牛客3750题 5分钟掌握滑动窗口最大值 面试官最爱考的优化技巧

一、问题理解

滑动窗口最大值问题要求我们给定一个整数数组和一个固定大小的窗口，窗口从数组最左端滑动到最右端，每次返回窗口内的最大值。例如：
输入: nums = [1,3,-1,-3,5,3,6,7], k = 3
输出: [3,3,5,5,6,7]

二、单调队列解法详解

优化解法使用‌双端队列(deque)‌维护一个单调递减的序列：

1. ‌队列存储的是元素下标‌而非值本身，便于判断元素是否在窗口内

2. ‌队列保持单调递减‌：新元素入队前，移除所有比它小的元素

3. ‌队首元素总是当前窗口的最大值‌

4. ‌定期清理过期元素‌：检查队首元素是否已超出窗口范围

三、完整代码

#include <vector>
#include <deque>
#include <stdexcept>
using namespace std;
class Solution {
  public:
    vector<int> maxInWindows(vector<int>& num, int size) {
        vector<int> result;
    deque<int> dq; // 存储下标，保证队列中元素对应值单调递减
    
    for (int i = 0; i < num.size(); ++i) {
        // 移除超出窗口范围的元素
        while (!dq.empty() && dq.front() <= i - size) {
            dq.pop_front();
        }
        
        // 维护单调递减队列
        while (!dq.empty() && num[dq.back()] < num[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        // 当窗口形成后开始记录结果
        if (i >= size - 1) {
            result.push_back(num[dq.front()]);
        }
    }
    
    return result;
    }
};

四、代码逐行解析

1. deque<int> dq：创建双端队列存储元素下标

2. 第一个while循环：移除超出窗口范围的队首元素

3. 第二个while循环：维护队列单调性，移除比当前元素小的队尾元素

4. dq.push_back(i)：当前元素入队

5. if (i >= k - 1)：当窗口形成后开始记录结果

五、复杂度分析

• 时间复杂度：O(n)，每个元素最多入队出队各一次

• 空间复杂度：O(k)，队列最多存储k个元素

六、总结

单调队列是解决滑动窗口类问题的利器，通过维护队列的单调性，我们能够高效获取窗口极值。掌握这个技巧对算法面试和实际开发都大有裨益。