LeetCode 239. 滑动窗口最大值

239. 滑动窗口最大值

解题思路

这是一个降本增笑的故事：

如果新员工比老员工强（或者一样强），把老员工裁掉。（元素进入窗口）
如果老员工 35 岁了，也裁掉。（元素离开窗口）
裁员后，资历最老（最左边）的人就是最强的员工了。

单调队列

• 右边入队，保持单调递减
• 左边出，对应的索引超出窗口的范围[i - k + 1, i]，出队

参考代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>();

        for(int i = 0; i < n; i ++) {
            while(!q.isEmpty() && nums[q.getLast()] <= nums[i]) {
                q.removeLast();
            }
            q.addLast(i);

            int left = i - k + 1;
            if(q.getFirst() < left) {
                q.removeFirst();
            }
            // 从第一个窗口开始
            if(i >= k - 1) {
                ans[i - k + 1] = nums[q.getFirst()];
            }
        }
        return ans;
    }
}