力扣hot100——239.滑动窗口最大值
题目链接： 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越靠后）同时还能力更强（数值越大）的，留着其他比它更早入职同时能力却更差的没有什么意义，统统开了；队首的虽然能力最强，但是年龄最大，一旦发现它超过年龄范围（不在滑动窗口的范围内），不用看能力就可以直接开了。
我悟了， 队尾比不过同龄人的删掉，队头超出时代区间的删掉，历史就是这么不断更迭的。