AcWing 79. 滑动窗口的最大值

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 79. 滑动窗口的最大值原题链接困难

作者：

cornerCao , 2019-01-25 14:58:52 , 所有人可见 , 阅读 6947

37

20

算法1

(单调队列) $O(n)$

首先，最直接的做法当然是模拟滑动窗口的过程，每向右滑动一次都遍历一遍窗口内的数字找最大的输出，这样的复杂度是$O(kn)$，我们可以考虑优化一下。窗口向右滑动的过程实际上就是将处于窗口的第一个数字删除，同时在窗口的末尾添加一个新的数字，这就可以用双向队列来模拟，每次把尾部的数字弹出，再把新的数字压入到头部，然后找队列中最大的元素即可。

为了更快地找到最大的元素，我们可以在队列中只保留那些可能成为窗口最大元素的数字，去掉那些不可能成为窗口中最大元素的数字。考虑这样一个情况，如果队列中进来一个较大的数字，那么队列中比这个数更小的数字就不可能再成为窗口中最大的元素了，因为这个大的数字是后进来的，一定会比之前早进入窗口的小的数字要晚离开窗口，那么那些早进入且比较小的数字就“永无出头之日”，所以就可以弹出队列。

于是我们维护一个双向单调队列，队列放的是元素的下标。我们假设该双端队列的队头是整个队列的最大元素所在下标，至队尾下标代表的元素值依次降低。初始时单调队列为空。随着对数组的遍历过程中，每次插入元素前，首先需要看队头是否还能留在队列中，如果队头下标距离i超过了k，则应该出队。同时需要维护队列的单调性，如果nums[i]大于或等于队尾元素下标所对应的值，则当前队尾再也不可能充当某个滑动窗口的最大值了，故需要队尾出队。始终保持队中元素从队头到队尾单调递减。依次遍历一遍数组，每次队头就是每个滑动窗口的最大值所在下标。

时间复杂度分析：每个元素最多入队出队一次，复杂度为$O(n)$

C++ 代码

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int>res;
        deque<int>q;
        for(int i = 0; i < nums.size(); i++){
            if(!q.empty() && i-q.front() >= k)//判断队头是否需要出队
                q.pop_front();
            while(!q.empty()&&nums[q.back()]<nums[i])//维护队列单调性
                q.pop_back();
            q.push_back(i);
            if(i >= k-1){
                res.push_back(nums[q.front()]);//取队头作为窗口最大元素
            }
        }
        return res;
    }
};

16 评论

旧手机换菜刀了啊 2023-07-12 21:53

这题解很强啊

王兆松 2022-06-12 07:28

每次把尾部的数字弹出，再把新的数字压入到头部，然后找队列中最大的元素即可。
这里对头和队尾反了吧

Eleanora 2022-03-13 17:50

有个想法啊，就是front哪里，会不会出现第一个超过窗口的大小了，弹出之后，第二个仍然超出窗口的大小。
把 if(!q.empty() && i-q.front() >= k)改为while(!q.empty() && i-q.front() >= k)会不会更稳妥一点呢

风好大 2022-08-26 09:16

不会，每次都会判断一下

晅 2021-12-05 20:57

能不能讲讲关于 i 的细节问题？

波牙锤 2021-12-27 09:34

vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int>res;
        deque<int>q; 
        for(int i=0;i<nums.size();i++)//循环枚举所有数组元素nums[i]的下标i
        {
            if(q.size()&&i-q.front()>=k)//队列不空且当前枚举到的元素下标i与队首(下标)之差大于窗口长度
                q.pop_front();//窗口向右滑动，队首出队；

            while(!q.empty()&&nums[q.back()]<nums[i])//有较大的nums[i]要入队，则删掉队列中所有较小的队尾元素后nums[i]才入队
                q.pop_back();
            q.push_back(i);//循环结束后下标i入队
            if(i>=k-1)//枚举到第k-1个元素后，每次枚举一个新的i都要找一次答案
                res.push_back(nums[q.front()]);//将队列当前队首下标对应的元素加入到答案数组
        }
        return res;
    }

晅 2021-12-27 12:57 回复了波牙锤的评论

谢谢老师！！

阿依土鳖 2022-03-03 22:48 回复了波牙锤的评论

太棒了，谢谢大佬

烟花易冷 2020-08-05 18:13

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int>res;// 最大值数组
        deque<int>q; // 双端队列
        for(int i = 0; i < nums.size(); i++)// 始终保持队列q单调递减
        {
            if(i - q.front() >= k)// 如果当前元素的下标与队头元素下标的距离超过窗口大小
                q.pop_front();// 队头出队
            while(!q.empty() && nums[q.back()] < nums[i])// 队列q不为空且 队列尾部比当前元素值小
                q.pop_back();// 队尾出队
            q.push_back(i);// 下标i入队
            if(i >= k - 1)// 输入次数大于窗口值
                res.push_back(nums[q.front()]);// 取队头作为窗口最大元素
        }
        return res;
    }
};