剑指 Offer 59 - I. 滑动窗口的最大值

同 239. 滑动窗口最大值

单调队列

用双端队列保存有可能是滑动窗口最大值的数字的下标。
在存入一个数字的下标之前，先判断队列里已有数字是否小于待存入的数字，若是，则这些数字不可能是滑动窗口最大值，将它们依次从队尾删除。
此时，队头元素为滑动窗口最大值。
如果队头元素已经从窗口滑出，则将滑出的数字从队头删除。
因为队头和队尾都有可能删除数字，所以需要使用双端队列。
因为队列中元素满足严格单调递减，所以这种单调性的队列一般称作单调队列。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];

        // 双端队列
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];

        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        res[0] = nums[deque.peekFirst()];

        for (int i = k; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();          // 将窗口最左侧元素移出队列
            }
            deque.offerLast(i);         // 窗口向右移动一个位置，将新元素加入队列
            res[i - k + 1] = nums[deque.peekFirst()];
        }
        return res;
    }
}

• 时间复杂度：O(n) ，n 是数组 nums 的长度，每一个下标恰好被放入队列一次，并且最多被弹出队列一次。
• 空间复杂度：O(k) ，双端队列最多同时存储 k（窗口大小）个元素。