LeetCode Hot100 239.滑动窗口最大值

题目：

给你一个整数数组?nums，有一个大小为?k?的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的?k?个数字。滑动窗口每次只向右移动一位。

返回?滑动窗口中的最大值?。

思路：

代码：

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++) {
            // 1.入
            while (!q.isEmpty() && nums[q.getLast()] <= nums[i]) {
                q.removeLast(); // 维护q的单调性
            }
            q.addLast(i); // 入队
            // 2.出( 弹出队首不在窗口内的元素 )
            if (i - q.getFirst() >= k) {
                q.removeFirst();
            }
            // 3.记录答案 
            if (i >= k - 1) {
                // 由于队首到队尾单调递减，所以窗口最大值就是队首
                ans[i - k + 1] = nums[q.getFirst()];
            }
        }
        return ans;
    }
}

滑动窗口问题三部曲：

1、入

2、出

3、记录答案