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

每次只取窗口中最大值，這個最大值可能在后面的滑動中保持不變，而比最大值小的值且在最大值之前出現(xiàn)的值沒必要保留，因此可以通過單調(diào)隊列利用這個特性。

這個單調(diào)隊列具有如下性質(zhì):

1.隊頭始終為當(dāng)前隊列的最大值

2.隊列具有單調(diào)性，隊尾為最小值

因此，用三個函數(shù)實現(xiàn)題目要求。

pop()，檢查當(dāng)前滑動窗口最后一個元素是否為單調(diào)隊列的隊頭，若不是則不用管，這說明該元素不是當(dāng)前單調(diào)隊列的最大值，在這之前就已經(jīng)被丟出單調(diào)隊列中。

push()，將當(dāng)前滑動窗口的第一個元素加入單調(diào)隊列中，把隊列中小于該元素的值全部丟出隊列。

getmax()，單調(diào)隊列的隊頭即為最大值。

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;}
};