牛客3750题解：滑动窗口最大值的单调队列解法
一、问题理解
牛客3750题要求找出数组中所有大小为k的滑动窗口中的最大值。这是一个经典的算法问题，在数据流处理、时间序列分析等领域有广泛应用。
二、算法核心思想
使用单调递减队列(deque)来维护当前窗口中的候选最大值：
队列头部始终是当前窗口的最大值
队列元素按从大到小排列
通过下标判断移除过期元素
三、完整代码实现（带注释）
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, int size) {
vector<int> result;
// 处理特殊情况：窗口大小为0或大于数组长度
if (size == 0 || size > num.size()) return result;
deque<int> dq; // 存储下标，维护单调递减队列
for (int i = 0; i < num.size(); ++i) {
// 移除超出窗口范围的元素
while (!dq.empty() && dq.front() <= (int)(i - size)) {
dq.pop_front();
}
// 维护单调递减性质
while (!dq.empty() && num[dq.back()] <= num[i]) {
dq.pop_back();
}
dq.push_back(i);
// 当窗口形成后开始记录结果
if (i >= (int)(size - 1)) {
result.push_back(num[dq.front()]);
}
}
return result;
}
};四、关键点解析
单调队列维护：
队列中存储的是元素下标而非值本身
新元素入队时会移除所有比它小的元素
窗口边界处理：
通过比较队首元素下标与i-size判断是否过期
只有当i >= size-1时才记录结果
时间复杂度：
每个元素最多入队出队各一次
总体时间复杂度为O(n)
五、常见问题解答
Q: 为什么使用deque而不是普通队列？ A: deque支持两端操作，便于同时处理队首过期元素和队尾维护单调性
Q: 如何处理重复最大值？ A: 算法会自动保留最右侧的最大值，保证后续窗口的正确性
Q: 空间复杂度是多少？ A: 最坏情况下O(k)，当数组单调递减时队列会存储整个窗口元素
原创内容 转载请注明出处
