Deque

双端队列

Sliding Window Maximum

• 经典的运用Deque构造monotonic decreasing queue的题目

• 因为window size is fixed, 所以跟sliding window没啥关系

class Solution {
    /*
    monotolic queue in decresing order, store index of element

    for loop to iterate each element from nums {
        1. from left to right, remove idx from queue which is out of range,
        2. from right to left, remove idx from queue which nums[idx] <= nums[i]
        3. queue.offer(i)
        4. update res if i >= k - 1
    }
    */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return new int[0];
        }
        int N = nums.length;
        int[] res = new int[N - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        int idx = 0;
        for (int i = 0; i < N; i++) {
            //from left to right, remove idx from queue which is out of range,
            while (!deque.isEmpty() && deque.peekFirst() <= i - k){
                deque.pollFirst();
            }
            //from right to left, remove idx from queue which nums[idx] <= nums[i]
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){
                deque.pollLast();
            }
            deque.offer(i);
            //skip the first few elements that is less than k
            if (i >= k - 1) {
                res[idx++] = nums[deque.peekFirst()];
            }
            
        }
        return res;
    }
}