一、题目解读
牛客3750题要求在一个给定的整数数组中,计算固定大小为k的滑动窗口内元素的最大值。例如,当窗口滑动时,需要实时输出每个窗口中的最大值序列。该问题考察对滑动窗口算法的理解,以及如何高效维护窗口内的元素关系。
二、解题思路
采用双端队列(deque)维护单调递减队列的巧妙解法。核心思想是:队列中仅存储数组下标,保证队头为当前窗口的最大值下标,并通过以下规则动态维护:
1. 当新元素进入窗口时,从队尾弹出所有小于新元素的元素,确保队列单调递减;
2. 当窗口左边界移动时,从队头弹出超出窗口范围的元素。
通过该策略,队头始终指向窗口内最大值,避免了对窗口内元素的重复遍历。
三、解题步骤
初始化结果数组与双端队列;
遍历数组,若队列不空且队头下标已超出窗口范围,弹出队头;
从队尾弹出所有小于当前元素的下标,保持队列单调递减;
将当前下标入队;
当窗口形成(即遍历至窗口大小-1时),记录队头元素值至结果数组;
遍历结束后返回结果。
四、代码和注释
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;
}
};
五、总结
本解法通过双端队列优化,将时间复杂度降至O(n),空间复杂度为O(k)。关键在于利用队列单调性避免重复比较,实现窗口滑动时的高效最大值获取。理解“单调队列维护”与“窗口边界处理”的逻辑是解决此类问题的核心。