文章目录
问题描述
解法一：优先队列（大顶堆）
我觉得，从题目中给出的信息应该就很直观的体现出这是 top K 问题了，既然是 top K 问题，很容易就能想到可以使用堆来解决问题
解题思路
- 如果堆存储的只是 nums[i]，那么我们并不能清楚当前的堆所在的位置，所以很自然的就能想到我们需要存储一个键值对，用于记录当前的数值和所映射的位置。而且堆顶为最大值，也就是窗口最大值，所以 nums[i] 很自然的就为
pair.first，而i就为pair.second。 - 首先将前
k个元素放入优先队列中，此时堆顶元素就是第一个窗口的最大值 - 在每次滑动的时候，就对应着出堆和入堆的过程
- 检查堆顶元素是否在当前窗口内，如果不在则移除，直到堆顶元素处于窗口内
- 将合法的堆顶元素加入结果集
可能有的人会问，这样堆中是不是会存在前面非窗口中的元素（即过期元素）？
答案是是的，但是那又有什么关系呢？它并不会影响结果的准确性。因为：
- 若过期元素是堆顶（最大元素），会被直接出堆
- 若过期元素是非堆顶元素，其大小小于当前堆顶，既不会干扰最大值选取，后续即便因上层元素出堆成为新堆顶，也会因索引校验失败被移除。
题中示例：nums = [1,3,-1,-3,5,3,6,7], k = 3，输出应为 [3,3,5,5,6,7]。
我们来通过堆的思路来简单解释一下：
- 初始时，将前
3个元素[1,3,-1]放入优先队列，堆顶为3，此时结果集添加3 - 加入元素
-3，优先队列中有[1,3,-1,-3]，堆顶还是3，且3的索引1在窗口[1,3]（i=3时，窗口范围为 1 到 3）内，结果集添加3 - 加入元素
5，优先队列中有[1,3,-1,-3,5]，堆顶是5，5的索引4在窗口[2,4]内，结果集添加5 - 以此类推，完成所有元素的处理
代码实现
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
// 维护一个堆，存储(值, 索引)对
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 < n; ++i) {
q.emplace(nums[i], i);
// 移除堆顶所有不在当前窗口[i-k+1, i]内的元素
while (q.top().second <= i - k) {
q.pop();
}
ans.push_back(q.top().first);
}
return ans;
}
};
复杂度分析
- 时间复杂度：
O(NlogN)。每个元素入堆和出堆的操作都是O(logN)，总共有N个元素。虽然在最坏情况下，每个元素可能会被弹出一次，但总体的时间复杂度仍然是O(NlogN)。 - 空间复杂度：
O(N)。在最坏情况下，堆可能需要存储所有元素，比如当数组是严格递增的时候，每个元素都会被加入堆中，且不会被提前弹出。
优先队列解法的核心矛盾
优先队列的核心优势是能快速获取最大值（O(1) 时间），但在滑动窗口场景中暴露出两个关键问题：
- 空间冗余：堆中会积累大量过期元素（已超出窗口范围）。例如当处理严格递增数组时，堆中会存储所有元素，空间复杂度达到
O(N)，远高于窗口大小k。 - 时间损耗：每次取最大值前需反复弹出堆顶过期元素，这些操作本质上是对无效数据的处理。在最坏情况下，每个元素可能被推入堆后又弹出，虽然整体复杂度仍为
O(NlogN)，但常数因子较大。
这些问题的根源在于优先队列的设计目标是全局维护最大值，而滑动窗口问题需要的是动态维护局部最大值—— 这就需要一种能精准管理窗口内有效元素的数据结构。
从 “全局维护” 到 “局部筛选” 的思路转变
通过解法一，我们可以观察到，其实在队列新增一个较大的元素，那么有些元素永远都不可能到达堆顶。
例如：假设此时 k = 4，且某一时刻，窗口中的内容为 [5, 1, 3, 4]，此时如果新增一个元素 6，你会发现这前面的元素永远都成不了 窗口中的最大元素，所以我们维护有些元素并没有价值。总结特性为：当新元素进入窗口时，所有比它小的旧元素都不可能再成为后续窗口的最大值。这个特性让我们可以提前筛选 目标元素，即有潜力称为最大值 的元素。
解法二：单调队列
单调队列的设计逻辑推导
基于上述观察，我们可以构建一个只保留 “有潜力成为最大值” 元素的队列，其设计逻辑如下：
- 队列存储索引而非值：既便于判断元素是否在窗口内（通过索引范围校验），又能通过索引获取对应值进行比较。
- 维持队列单调性：要求队列中元素对应的值严格递减。这样队头元素自然就是当前窗口的最大值，无需像优先队列那样通过堆结构维护。
- 动态清理无效元素：
- 移除窗口外的元素（通过队头索引与当前位置的比较）
- 移除所有小于新入队元素的值（这些元素已失去成为最大值的可能）
这种设计完美解决了优先队列的缺陷：
- 空间上，队列大小被严格控制在
O(k)以内，因为任何时刻队列中最多包含当前窗口内的元素 - 时间上，每个元素仅入队和出队各一次，总操作次数为
O(N)，且避免了优先队列的logN级别的元素调整成本
解题步骤
- 维护一个存储元素索引的双端队列，队列内元素对应的值保持递减
- 对于每个新元素，移除队列中所有小于当前元素的值（因为它们不可能成为后续窗口的最大值）
- 移除队列中超出当前窗口范围的元素
- 将当前元素索引加入队列
- 当窗口形成后，队列头部元素即为当前窗口的最大值
同样结合示例说明：
- 处理索引
0（值1）：队列空，直接入队，队列是 [0] - 处理索引
1（值3）：3大于1，移除索引0，队列空，入队1，队列是[1] - 处理索引
2（值-1）：-1小于3，入队2，队列是[1,2]，此时窗口形成（i=2 >= 2），结果集添加nums [1]=3 - 处理索引
3（值-3）：先判断队头1是否<= 3-3=0，1>0，不弹出；-3小于-1，入队3，队列是[1,2,3]，窗口形成，结果集添加3 - 处理索引
4（值5）：先判断队头1 <= 4-3=1，1<=1，弹出1；此时队头是2，nums[2]=-1 <5，弹出2；队头是3，nums[3]=-3 <5，弹出3；队列空，入队4，窗口形成，结果集添加5 - 以此类推，完成后续元素的处理
代码实现
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> q; // 存储元素索引，按值降序排列
vector<int> ans;
for (int i = 0; i < n; ++i) {
// 移除窗口外的过期元素（队头）
if (!q.empty() && q.front() <= i - k) {
q.pop_front();
}
// 维护队列单调性：删除队尾所有比当前元素小的值
while (!q.empty() && nums[q.back()] < nums[i]) {
q.pop_back();
}
q.push_back(i); // 当前元素入队
// 窗口形成后，队头即为最大值
if (i >= k - 1) {
ans.push_back(nums[q.front()]);
}
}
return ans;
}
复杂度分析
- 时间复杂度：
O(N)。每个元素只会入队和出队各一次，总操作次数为O(N)。虽然代码中有嵌套的循环，但每个元素最多被弹出一次，所以整体时间复杂度是线性的。 - 空间复杂度：
O(k)。队列中最多存储k个元素，因为在任何时候，队列中的元素都是当前窗口或可能在后续窗口中成为最大值的元素，且数量不会超过k。
两种方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 优势 | 劣势 |
|---|---|---|---|---|
| 优先队列 | O(NlogN) | O(N) | 实现简单，思路直观，不需要太多的技巧 | 时间复杂度较高，空间占用较大，在数据量很大时性能会有明显下降 |
| 单调队列 | O(N) | O(k) | 时间和空间效率更优，适用于大规模数据处理 | 实现稍复杂，需要理解单调队列的维护逻辑，对初学者来说有一定难度 |