力扣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越靠后）同时还能力更强（数值越大）的，留着其他比它更早入职同时能力却更差的没有什么意义，统统开了；队首的虽然能力最强，但是年龄最大，一旦发现它超过年龄范围（不在滑动窗口的范围内），不用看能力就可以直接开了。

我悟了， 队尾比不过同龄人的删掉，队头超出时代区间的删掉，历史就是这么不断更迭的。