滑动窗口最大值

1. 题目呈现

难度等级：🔴 困难
核心考察点：单调队列、堆、滑动窗口

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：

滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：
输入：nums = [1], k = 1
输出：[1]

2. 解题思路拆解

方法：单调队列 (Monotonic Queue)

如果我们使用普通队列，入队出队是 $O(1)$，但找最大值是 $O(k)$，总时间复杂度会变成 $O(nk)$，会超时。我们需要一个能同时支持：

入队/出队
快速获取最大值 的数据结构。

单调队列的核心思想是：如果一个选手比你小，还比你老（先入队），那他就永远不可能成为最大值了。

队列存储：队列中存储的是数组下标（存下标方便判断元素是否滑出了窗口）。
保持单调递减：
- 当新元素 nums[i] 准备入队时，将队尾所有小于 nums[i] 的元素统统移除（因为 nums[i] 更大且更新，只要 nums[i] 在，那些小的永远不可能是最大值）。
- 将 nums[i] 的下标加入队尾。
- 此时，队头元素对应的数值一定是当前窗口的最大值。
移除过期元素：
- 检查队头下标是否已经滑出窗口（即 headIndex <= i - k）。如果是，将队头移除。
记录答案：
- 当窗口形成（即 i >= k - 1）时，队头元素即为当前窗口最大值，加入答案数组。

3. 代码实现

javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    // 存储的是下标
    const deque = [];
    const result = [];
    
    for (let i = 0; i < nums.length; i++) {
        // 1. 入队维护：如果新来的比队尾大，队尾就没用了，移除
        while (deque.length > 0 && nums[i] >= nums[deque[deque.length - 1]]) {
            deque.pop();
        }
        
        // 加入当前元素下标
        deque.push(i);
        
        // 2. 检查队头是否过期
        // 当前窗口范围是 [i - k + 1, i]
        // 如果队头下标 < i - k + 1，说明已经滑出左边界
        if (deque[0] <= i - k) {
            deque.shift();
        }
        
        // 3. 记录最大值
        // 当窗口完全形成后开始记录（i 从 k-1 开始）
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }
    
    return result;
};

代码执行演示

输入 nums = [1, 3, -1, -3, 5], k = 3

i=0, num=1: 队列为空。q=[0(1)]。
i=1, num=3: 3 > 1，0出队。q=[1(3)]。
i=2, num=-1: -1 < 3，保留。q=[1(3), 2(-1)]。
- 窗口形成 (i=2 >= 2)。队头是 nums[1]=3。res=[3]。
i=3, num=-3: -3 < -1，保留。q=[1(3), 2(-1), 3(-3)]。
- 检查过期：队头 1，当前边界 3-3=0。1 > 0，未过期。
- 最大值 nums[1]=3。res=[3, 3]。
i=4, num=5:
- 5 > -3，3出队。
- 5 > -1，2出队。
- 5 > 3，1出队。
- q=[4(5)]。
- 最大值 nums[4]=5。res=[3, 3, 5]。

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。每个元素最多进队一次，出队一次。虽然有 `while` 循环，但均摊下来是线性的。
空间复杂度	$O(k)$。双端队列最多存储 `k` 个元素的下标。

滑动窗口最大值 ​

1. 题目呈现 ​

2. 解题思路拆解 ​

方法：单调队列 (Monotonic Queue) ​

3. 代码实现 ​

代码执行演示 ​