LeetCode：239 滑动窗口最大值 双端队列 O(n)

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

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

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

输出: [3,3,5,5,6,7]

解释:

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

进阶：

你能在线性时间复杂度内解决此题吗？

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/sliding-window-maximum

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

使用双端队列存储一个滑动窗口内的元素下标，这个双端队列必须满足以下几个特征：

• 队头元素是滑动窗口内最大元素的下标
• 从队头到队尾的下标对应的元素必须递减
• 存储的下标必须在滑动窗口内

维护性质2

不断枚举滑动窗口的右端点

r

，如果

nums[r]

比队尾元素对应的数

nums[back()]

大，那么不断弹出队尾元素，直到队尾大于

nums[r]

（因为比新数

nums[r]

小的数，都不能作为区间的最大元素了，可以舍弃），新元素入队尾

维护性质3

因为右端点推进了，左端点

l

也要推进，还要检查当前区间的最大值（队头存储的下标）是否已经超过了当前的窗口，如果是，那么队头要弹出

保存下标是为了快速判断存储的元素是否超过滑动窗口的范围，而元素递减保证了最大元素超出区间时被弹出，队头仍然是最大元素

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {
        vector<int> ans;
        if(k==0) return ans;
        if(k==1) return nums;
        deque<int> q;
        // 初始化队列
        for(int i=0; i<k; i++) 
        {
            while(!q.empty() && nums[i]>nums[q.back()]) 
                q.pop_back();
            q.push_back(i);
        }
        ans.push_back(nums[q.front()]);
        // 开始滑动，弹出超出区间或小的元素，进来新元素
        // l+k-1：区间右端点下标
        for(int l=1; l+k-1<nums.size(); l++)
        {
            if(l-1==q.front()) q.pop_front();
            while(!q.empty() && nums[l+k-1]>nums[q.back()]) 
                q.pop_back();
            q.push_back(l+k-1);
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};