LeetCode刷题记录：（6）滑动窗口最大值

LeetCode传送通道

难题不难，快去通关！

class Solution {
   
    public int[] maxSlidingWindow(int[] nums, int k) {
   
        int n = nums.length;
        // 如果数组长度不超过k个，排序返回其中最大值即可
        if(n<=k){
   
            Arrays.sort(nums);
            return new int[]{
   nums[n-1]};
        }
		
		// 下面是核心代码
        int[] result = new int[n-k+1];
        Deque<Integer> queue = new LinkedList<>();
        
        // 1.为了方便理解，这里先处理前k个数，相当于初始化单调队列和结果数组
        for(int i=0; i<k; i++){
   
            // 新数据入队时，把前面小于该数据的元素移出队列
            offerLastAndPollSmallBefore(queue, nums[i]);
        }
        // 因为队列头部始终是窗口最大值
        result[0] = queue.peekFirst();

        // 2.处理后续数据（别怕，仅仅多了一个判断而已）
        for(int i=k; i<n; i++){
   
            // 判断当前队列的最大元素是否是旧窗口的左边界元素，
            // 如果是则弹出，因为新的窗口将不再包含该元素（可以自行画图理解一下）
            if(queue.peekFirst() == nums[i-k]){
   
                queue.pollFirst();
            }
            offerLastAndPollSmallBefore(queue, nums[i]);
            result[i-k+1] = queue.peekFirst();
        }
        return result;
    }
    
	// 新数据val入队时，把前面小于val的元素移出队列
    private void offerLastAndPollSmallBefore(Deque<Integer> queue, int val){
   
        while (!queue.isEmpty() && val > queue.getLast()){
   
                queue.pollLast();
            }
            queue.offerLast(val);
    }
}