239. 滑動(dòng)窗口最大值 - 力扣（LeetCode）

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

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

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

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

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

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

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

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

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