牛客3750题滑动窗口最大值解析:双端队列优化解法与代码详解
一、题目解读
牛客3750题要求在一个给定的整数数组中,计算固定大小为k的滑动窗口内元素的最大值。例如,当窗口滑动时,需要实时输出每个窗口中的最大值序列。该问题考察对滑动窗口算法的理解,以及如何高效维护窗口内的元素关系。
二、解题思路
采用双端队列(deque)维护单调递减队列的巧妙解法。核心思想是:队列中仅存储数组下标,保证队头为当前窗口的最大值下标,并通过以下规则动态维护:
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)。关键在于利用队列单调性避免重复比较,实现窗口滑动时的高效最大值获取。理解“单调队列维护”与“窗口边界处理”的逻辑是解决此类问题的核心。
原创内容 转载请注明出处