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