代码随想录 栈与队列 test 6

239. 滑动窗口最大值 - 力扣（LeetCode）

每次只取窗口中最大值，这个最大值可能在后面的滑动中保持不变，而比最大值小的值且在最大值之前出现的值没必要保留，因此可以通过单调队列利用这个特性。

这个单调队列具有如下性质:

1.队头始终为当前队列的最大值

2.队列具有单调性，队尾为最小值

因此，用三个函数实现题目要求。

pop()，检查当前滑动窗口最后一个元素是否为单调队列的队头，若不是则不用管，这说明该元素不是当前单调队列的最大值，在这之前就已经被丢出单调队列中。

push()，将当前滑动窗口的第一个元素加入单调队列中，把队列中小于该元素的值全部丢出队列。

getmax()，单调队列的队头即为最大值。

class Solution {
private:class MyQueue{public:deque<int> queue;void pop(int num){if(!queue.empty() && num == queue.front())queue.pop_front();}void push(int num){while(!queue.empty() && num > queue.back()){queue.pop_back();}queue.push_back(num);}int getMax(){return queue.front();}};
public:MyQueue queue;vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> res;for(int i = 0; i < k; i++){queue.push(nums[i]);}res.push_back(queue.getMax());for(int i = k; i < nums.size(); i++){queue.pop(nums[i - k]);queue.push(nums[i]);res.push_back(queue.getMax());}return res;}
};