时间轴

2026-03-11

init

题目：

P239 滑动窗口最大值

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

最大堆+懒删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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 存起来就能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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]] >= ...。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
        }
};