Leetcode 239

题目要求

整数数组nums，滑动窗口长度k，从nums最左侧开始每次移动一位，记录每个位置下的滑动窗口内元素的最大值。

核心算法和原理

• 维护动态的窗口最大值：存在单调性

• 假定有一个数据结构维护窗口的候选最大值：每次移动后，如果新加入窗口的值x比「窗口末尾的几个元素」要大，则「窗口末尾的几个元素」不可能成为最大值的候选，移出，直到遇到末尾的比x大的元素，才将x移入；同时将上一个位置的队首移出；

• 显然，可以用一个双端队列维护这个窗口候选最大值；同时这个队列一定满足从队首到队尾单调递减，故这就是一个「单调队列」

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans(nums.size() - k + 1);
        deque<int> q;
        for (int i = 0; i < nums.size(); i++) {
            // 单调队列入队尾
            while (!q.empty() && nums[q.back()] <= nums[i]) {
                q.pop_back();
            }
            q.push_back(i);

            // 单调队列出队首
            if (q.front() <= i - k) {
                q.pop_front();
            }

            // 记录答案
            if (i - k >= -1) {
                ans[i - k + 1] = nums[q.front()];
            }
        }
        return ans;
    }
};