使用双端队列维护滑动窗口最大值，核心是保持队列递减。遍历数组，移除队首过期索引，从队尾删除小于等于当前值的索引，确保队首始终为当前窗口最大值。当i≥k-1时，将队首对应值加入结果。时间复杂度O(n)，空间复杂度O(k)。
在C++中，使用队列实现滑动窗口最大值问题，最高效的方法是利用双端队列（deque）来维护窗口内可能成为最大值的元素索引。这种方法可以在O(n)时间复杂度内解决该问题。
问题描述
给定一个数组 nums 和滑动窗口大小 k，从左到右每次滑动一格，输出每个窗口中的最大值。示例：
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
输出：[3, 3, 5, 5, 6, 7]
核心思路：单调双端队列
我们维护一个递减的双端队列 deque，存储的是数组元素的索引，而非值本身。队列前端始终保存当前窗口最大值的索引。
关键规则：
- 遍历数组时，若队首索引已不在当前窗口范围内，将其弹出。
- 在将当前元素索引加入队列前，从队尾开始删除所有对应值小于等于当前值的索引（保持递减性）。
- 当遍历到第 i 个元素且 i >= k-1 时，说明窗口已形成，此时队首即为当前窗口最大值。
C++ 实现代码
#include#include
using namespace std;
vector
deque
vector
for (int i = 0; i
// 移除队首超出窗口范围的索引
if (!dq.empty() && dq.front() == i - k)
dq.pop_front();
// 从队尾移除所有小于等于当前值的元素索引
while (!dq.empty() && nums[dq.back()]
dq.pop_back();
// 当前元素索引入队
dq.push_back(i);
// 窗口大小达到k后，记录最大值
if (i >= k - 1)
result.push_back(nums[dq.front()]);
}
return result;
}
算法特点与注意事项
时间复杂度：O(n)，每个元素最多入队和出队一次。
空间复杂度：O(k)，双端队列中最多保存k个元素。
立即学习“C++免费学习笔记（深入）”；
注意点：
- 队列中存的是索引，方便判断是否滑出窗口。
- 比较时用 nums[dq.back()] 而不是直接比较索引。
- 条件 nums[dq.back()]
基本上就这些，掌握单调队列的思想后，类似问题也能轻松应对。
