題目鏈接： 239. 滑動窗口最大值 - 力扣（LeetCode）

優先級隊列

優先級隊列自動按照大小排序，隊首即為最大元素，但取隊首時要注意元素是否在滑動窗口內，如果不在則彈出。

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {priority_queue<pair<int,int>> q;//（元素值，元素索引）//在第一個滑動窗口找最大元素for(int i=0;i<k;i++){q.emplace(nums[i],i);}vector<int> res={q.top().first};//移動窗口for(int i=k;i<nums.size();i++){q.emplace(nums[i],i);//移除不在窗口范圍內的元素while(q.top().second<=i-k){q.pop();}res.push_back(q.top().first);}return res;}
};

• 時間復雜度：O(nlogn) 每個元素都被插入和刪除一次
• 空間復雜度：O(n)

單調隊列

同一個窗口內，如果右側元素大于左側元素，那么左側元素不必考慮，因為此時窗口內的最大元素一定不是左側元素，并且當窗口向右移動時左側元素可能不在窗口中，因此永久移除這樣的左側元素。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {deque<int> q;for(int i=0;i<k;i++){while(!q.empty()&&nums[i]>=nums[q.back()]){q.pop_back();//移除小于右側元素的值}q.push_back(i);}vector<int> ans={nums[q.front()]};for(int i=k;i<nums.size();i++){//移除小于右側元素的值while(!q.empty()&&nums[i]>=nums[q.back()]){q.pop_back();}q.push_back(i);//移除不在窗口范圍內的元素while(q.front()<=i-k){q.pop_front();}ans.push_back(nums[q.front()]);}return ans;}

• 時間復雜度：O(n) 遍歷整個數組
• 空間復雜度：O(k)

引用評論區的兩句話來加深對單調隊列的理解：

我悟了，隊尾只要有更年輕（i越靠后）同時還能力更強（數值越大）的，留著其他比它更早入職同時能力卻更差的沒有什么意義，統統開了；隊首的雖然能力最強，但是年齡最大，一旦發現它超過年齡范圍（不在滑動窗口的范圍內），不用看能力就可以直接開了。

我悟了， 隊尾比不過同齡人的刪掉，隊頭超出時代區間的刪掉，歷史就是這么不斷更迭的。