leetcode热题100 P239 滑动窗口最大值

---

时间轴

时间轴

2026-03-11

init

单调队列，大顶堆，懒删除

---

题目：

P239 滑动窗口最大值

https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked

最大堆+懒删除

#include <vector>
#include <queue>
#include <unordered_map>
using std::vector;
using std::priority_queue;
using std::unordered_map;

class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int> &nums, int k)
        {
                priority_queue<int> max_heap;
                unordered_map<int, int> umap;
                vector<int> ret;

                int n = nums.size();

                for (int i = 0; i < k; i++) {
                        max_heap.push(nums[i]);
                        umap[nums[i]]++;
                }

                for (int i = 0; i <= n - k; i++) {
                        while (!max_heap.empty() && umap[max_heap.top()] == 0)
                                max_heap.pop();

                        ret.push_back(max_heap.top());

                        if (i + k < n) {
                                umap[nums[i]]--;

                                max_heap.push(nums[i + k]);
                                umap[nums[i + k]]++;
                        }
                }

                return ret;
        }
};

其实不用umap来实现懒删除，如果大顶堆中存值的同时也把 index 存起来就能实现懒删除

#include <vector>
#include <queue>
#include <utility>

using std::vector;
using std::priority_queue;
using std::pair;

class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int> &nums, int k)
        {
                int i, n = nums.size();
                priority_queue<pair<int, int> > q;

                for (i = 0; i < k; ++i)
                        q.emplace(nums[i], i);

                vector<int> ans = { q.top().first };

                for (i = k; i < n; ++i) {
                        q.emplace(nums[i], i);

                        while (q.top().second <= i - k) // 不着急删除，可以根据其index判断是否在内部
                                q.pop();

                        ans.push_back(q.top().first);
                }
                return ans;
        }
};

复杂度O(nlogn)

推荐的方法是单调队列：使用的是 单调递减双端队列 (Monotonic Decreasing Deque) 的方法。

deque<int> q：存储的是数组的下标 (index)，而不是具体的数值。

这个队列维护了一个性质：队列中的下标对应的数值是单调递减的。即nums[q[0]] >= nums[q[1]] >= ...。

单调队列

#include <vector>
#include <queue>

using std::vector;
using std::deque;

class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int> &nums, int k)
        {
                int n = nums.size();
                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 < n; ++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;
        }
};

acm mode rewrite

#include <cstdio>
#include <queue>
#include <utility>
#include <vector>

using std::vector;
using std::priority_queue;
using std::pair;

int main()
{
        int i, n, k;
        priority_queue<pair<int, int>, vector<pair<int, int> >, std::less<pair<int, int> > >
                max_heap;

        scanf("%d %d", &n, &k);

        vector<int> vec(n);

        for (i = 0; i < n; i++)
                scanf("%d", &vec[i]);

        for (i = 0; i < k; i++)
                max_heap.push({ vec[i], i });

        printf("%d ", max_heap.top().first);

        for (; i < n; i++) {
                while (!max_heap.empty() && i - max_heap.top().second >= k) // 注意max_heap.empty()否则会死循环
                        max_heap.pop();

                max_heap.push({ vec[i], i });

                printf("%d ", max_heap.top().first);
        }
}