239. 滑动窗口最大值

滑动窗口对应的数据结构是双端队列。

难点在于，窗口移动时，最大值可能掉出窗口，需要重新找出窗口内的最大值，时间复杂度为O((n-k+1)k)：

• 大小为n的数组中存在n-k+1个大小为k的窗口
• 每个窗口内在k个元素中找出最大值

最好是把第二个时间简化到O(1)

于是，联想到单调栈，每进来一个元素，都可以直接找出当前的最大值/最小值。

因此，需要做到以下几点：

• 当队首元素等于已经被删除的元素nums[i-1]，那么将队首元素删掉
• 入队时要保证队列保持非严格递减，保证栈底元素（队首元素）为最大值。
• 当i大于等于0时，表示窗口已经构建出来，需要将当前的最大值（队首元素）记录在数组中。

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[] ans = new int[nums.length - k + 1];
        for (int j = 0, i = 1 - k; j < nums.length; ++i, ++j) {
            if (i > 0 && deque.peekFirst() == nums[i - 1]) {
                deque.removeFirst();
            }
            while (!deque.isEmpty() && deque.peekLast() < nums[j]) {
                deque.removeLast();
            }
            deque.addLast(nums[j]);
            if (i >= 0) ans[i] = deque.peekFirst();
        }
        return ans;
    }
}