leetcode 239 滑动窗口最大值

题目

题解

1. 优先队列

使用大根堆，大根堆的堆顶元素就是最大值，此时我们只需要维护k个元素的大根堆即可，当超过k个，就弹出最左边的元素

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> ans={q.top().first};
        for(int i=k;i<nums.size();++i){
            q.emplace(nums[i],i);
        while(q.top().second<=i-k){
            q.pop();
        }
        ans.push_back(q.top().first);
       }
        return ans;
    }
};

2. 单调队列

使用单调队列，将最大值保留在队列中

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int q[100010];
        int hh=0,tt=-1;
        vector<int>ans;
        for(int i=0;i<k;i++){
            while(hh<=tt&&nums[i]>=nums[q[tt]])tt--;
            q[++tt]=i;
        }
        ans.push_back(nums[q[hh]]);
        for(int i=k;i<nums.size();i++){
            while(hh<=tt&&nums[i]>=nums[q[tt]])tt--;
            q[++tt]=i;
            while(q[hh]<=i-k){
                hh++;
            }
            ans.push_back(nums[q[hh]]);
        }
        return ans;
    }
};