算法题解

LeetCode Hot 100 | 11. 滑动窗口最大值

通过自定义单调递减队列，在 O(N) 时间内求解每个滑动窗口的最大值。

LeetCodeHot100滑动窗口C++面试算法

核心思路：单调队列

为什么不能用普通队列？

普通队列只能先进先出，想要在 O(1)O(1) 时间内找到队列中的最大值是不可能的（通常需要 O(k)O(k) 遍历）。

单调队列的定义：

我们需要维护一个队列，使得队列中的元素 单调递减（队头始终是当前窗口的最大值）。

为了实现这一点，我们需要自定义 push 和 pop 的规则：

  1. 入队 (push) —— 优胜劣汰：

    • 当我们尝试把一个新元素 val 放进队尾时，如果发现队尾原本的元素比 val 小，说明那些元素既比 val小（能力差），又比 val 进来的早（寿命短），它们在 val 存在的窗口期内永远不可能成为最大值。
    • 操作：直接把这些"累赘"从队尾踢出 (pop_back)，直到队尾元素大于 val 或队列为空，再把 val 放进去。

  2. 出队 (pop) —— 身份核验：

    • 当滑动窗口向右移动，索引 i−ki-k 的元素需要移出窗口。
    • 关键判断：我们只需要检查 队头元素 是否等于这个要移除的元素。
      • 如果相等：说明这个最大值正是我们要移除的那个老将，必须 pop_front。
      • 如果不等：说明这个要移除的元素早在之前 push 更大元素时，就已经被"优胜劣汰"给踢出去了。它不在队列里，所以不需要做任何操作。

代码实现

class Solution {
private:
    // 自定义单调队列类
    class MonotonicQueue {
    public:
        deque<int> dq; // 双端队列：支持头尾操作

        // 1. 入队：维护单调递减性质
        // 核心口诀：比我小还比我老的，统统卷铺盖走人
        void push(int val) {
            while (!dq.empty() && val > dq.back()) {
                dq.pop_back();
            }
            dq.push_back(val);
        }

        // 2. 出队：只有当要移除的元素恰好是队头最大值时，才真正弹出
        // 否则，说明它早在 push 阶段就被更大的元素挤走了
        void pop(int val) {
            if (!dq.empty() && val == dq.front()) {
                dq.pop_front();
            }
        }

        // 3. 获取最大值：永远是队头
        int max() {
            return dq.front();
        }
    };

public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MonotonicQueue window;
        vector<int> result;
        
        // Step 1: 先初始化第一个窗口
        for (int i = 0; i < k; i++) {
            window.push(nums[i]);
        }
        result.push_back(window.max()); // 记录第一个窗口的最大值
        
        // Step 2: 窗口开始滑动
        for (int i = k; i < nums.size(); i++) {
            // A. 移除旧元素 (nums[i-k])
            window.pop(nums[i - k]); 
            
            // B. 加入新元素 (nums[i])
            window.push(nums[i]);    
            
            // C. 记录当前窗口最大值
            result.push_back(window.max());
        }
        
        return result;
    }
};

复杂度分析

这是一个经典的 均摊复杂度 (Amortized Analysis) 案例。

  • 时间复杂度: O(N)O(N)
    • 乍一看 push 中有一个 while 循环，似乎是 O(k)O(k)？
    • 其实不然：数组中的每一个元素，最多只会被 push 进队列 一次，也最多会被 pop 出队列 一次。
    • 没有任何元素会被反复进出，所以总的操作次数与 NN 成线性关系。
  • 空间复杂度: O(K)O(K)
    • 队列中最多存储 KK 个元素（当数组本身是单调递减时，队列会存满 KK 个）。

关键点备忘

  1. 队列存什么？
    • 本解法存的是 数值 (Value)。
    • 另一种流派：队列存 下标 (Index)。存下标的好处是判断 pop 时不需要比对数值，而是直接看 index <= i-k 即可。但存数值逻辑更直观，更符合"单调队列"的数据结构定义。
  2. deque 的必要性：
    • 我们需要 push_back (正常入队), pop_back (维护单调性), pop_front (滑动窗口移出), front (获取最大值)。只有双端队列 deque 能同时满足这四个操作。
  3. 场景拓展：
    • 单调队列不仅仅用于滑动窗口最大值，它在 动态规划 (DP) 优化 中也非常重要（例如：优化形如 dp[i]=max⁡(dp[j])+val[i]dp[i] = \max(dp[j]) + \text{val}[i] 且 jj 有范围限制的转移方程）。