滑动窗口最大值

题目

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sliding-window-maximum

解题方法

首先在大小为n的格子中k个单位为一个窗口
那么会有n-k+1个窗口
我们可以用双向队列来模拟窗口的滑动
维护一个单调递减栈
可能说起来会比较抽象
我们拿他的样例举例子
[1,3,-1,-3,5,3,6,7]
一开始队列为空所以直接入栈
队列:[1]
接着3入栈 因为我们要维护单调递减栈所以3入栈会破坏
那么我们把前面所有比3小的弹出去
队列:[3]
-1入栈
队列:[3,-1]
此时已经形成一个窗口了
并且3 -1属于第一个窗口 要是不属于要弹掉
那么res[3]
第一个窗口的最大值就拿到啦!
-3入栈
队列:[3,-1,-3]
res[3,3]
5入栈
队列:[5]因为5比前面都大会破坏单调递增栈 前面全部弹出
res[3,3,5]
3入栈
队列:[5,3]
res[3,3,5,5]
6入栈
队列:[6]因为依然要满足单调递减栈 前面全部弹出
res:[3,3,5,5,6]
7入栈
队列:[7]前面全部弹出
res:[3,3,5,5,6,7]
结果就出来了啦!

AC代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> dq;
        for(int i=0;i<nums.size();i++)
        {
            while(!dq.empty() && nums[i] > nums[dq.back()])
            {
                dq.pop_back();
            }
            dq.push_back(i);
            if(i >= k && nums[i - k] == nums[dq.front()])
            {
                dq.pop_front();
            }
            if(i >= k-1)
            {
                res.push_back(nums[dq.front()]);
            }
        }
        return res;
    }
};
Last modification:June 27th, 2020 at 11:42 am
如果觉得我的文章对你有用,请随意赞赏