当前位置：首页 > article >正文

leetcode 239. 滑动窗口最大值

article 2025/3/1 23:50:27

题目如下
在这里插入图片描述

数据范围
在这里插入图片描述

观察数据范围如果枚举所有的窗口再求他们的最大值肯定是超时。
那么我们可以按照定长滑动窗口的思路：用一个长度为k的窗口从前往后直到最后面。
显然这样做只需要维护最大值就行，那么什么样的数据结构可以自动帮我们维护最大值呢？
显然是优先队列（大根堆）同时我们还需要存储每个数字对应的下标，当根上面的数的下标
落在滑动窗口内的时候把这个数送入答案，否则在while循环中删除到这个位置的值在滑动窗口为止。

通过代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        if(n == 1)return nums;
        vector<int> ans;
         priority_queue<pair<int, int>> q;
         for(int i = 0;i < k;i++){
            q.emplace(nums[i],i);
         }
         ans.push_back(q.top().first);
         for(int i = k;i < n;i++){
            q.emplace(nums[i],i);
            while(q.top().second <= i - k)q.pop();
            ans.push_back(q.top().first);
         }
            return ans;
        }
    
};