滑动窗口最大值
class Solution { private: class MyQueue{ public: deque<int> que; // 使用双端队列deque来实现单调队列 void pop(int value){ // 每次弹出的时候,比较当前要弹出的数值是否等于队列出口元素的数值,如果相等则弹出。左端弹出 if (!que.empty() && value == que.front()) { que.pop_front(); } } // 入队操作,如果push的数值大于入口元素的数值,那么就将队列右端端的数值弹出,直到push的数值小于等于队列入口元素的数值为止。循环弹出所有小于push值的值 // 这样,每次操作都把比value小的全部弹出,就保持了队列里的数值是单调从大到小的了。 void push(int value) { while (!que.empty() && value > que.back()) { que.pop_back(); } que.push_back(value); } int front() { return que.front(); } }; public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { MyQueue que; vector<int> result; for(int i = 0; i < nums.size(); i++){ que.push(nums[i]); if(i == k - 1) { result.push_back(que.front()); // 记录对应的最大值 } if(i >= k ){ que.pop(nums[i - k]); result.push_back(que.front()); // 记录对应的最大值 } } return result; } };
主要难点在于自己构造一个单调递增队列,省去排序的麻烦
其实思路就是维护这个滑动窗口的时候只关注入队的时候的情况,入队的时候是最大值,那就清空队列,入队的时候不是最大值,那就把比他小的值清空。这样的话,队首总是最大值了
标签:Day28,队列,value,front,que,数值,push,LeetCode,刷题 From: https://www.cnblogs.com/tianmaster/p/16933875.html