好的，我们这次来详细讲解 LeetCode 第 239 题「滑动窗口最大值」。
这是一道高频且经典的题目，结合了滑动窗口与单调队列的思想。

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]

提示

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

2. 题意理解

我们要在数组上维护一个长度为 k 的窗口，每次窗口右移一格，然后快速得到当前窗口内的最大值。
直接对每个窗口扫描求最大值，时间复杂度是 O(n*k)，在 n 最大为 10^5 时会超时。
所以我们需要一种高效维护窗口最大值的方法。

3. 思路演进

3.1 暴力法（不可行）

对每个窗口遍历 k 个元素找最大值。
时间复杂度 O((n-k+1)k) ≈ O(nk)，n 很大时太慢。

3.2 使用堆（优先队列）

我们可以用一个最大堆（大顶堆）来快速得到当前窗口的最大值。
堆中存储 (值, 索引)，这样当窗口滑动时，如果堆顶元素的索引不在当前窗口范围内，就弹出它，直到堆顶元素在当前窗口内。

步骤：

1. 初始化最大堆（Python 用 heapq 但存负数，或使用 (-nums[i], i)）。
2. 先将前 k 个元素加入堆。
3. 堆顶就是第一个窗口的最大值。
4. 窗口右移：加入新元素，循环检查堆顶是否在窗口内（索引 >= 当前窗口左边界），不在就弹出。
5. 堆顶即为当前窗口最大值。

复杂度：每个元素入堆出堆一次，堆操作 O(log n)，总复杂度 O(n log n)。可行，但可以优化到 O(n)。

3.3 单调队列（最优解）

我们希望在 O(1) 时间内获得当前窗口的最大值，并且维护这个“候选最大值”的结构在窗口滑动时能快速更新。

单调队列（Monotonic Queue）思想：

• 使用一个双端队列（deque）存储可能成为窗口最大值的元素的索引。
• 队列中的元素值从队首到队尾是递减的（队首是当前窗口最大值）。
• 当窗口滑动时：
  1. 移除队首过期索引（如果队首索引等于 i-k，说明它已经不在窗口内，弹出队首）。
  2. 从队尾开始，将所有小于当前新元素 nums[i] 的索引弹出（因为它们不可能再成为最大值了）。
  3. 将当前元素索引加入队尾。
  4. 当窗口形成后（i >= k-1），队首索引对应的值就是当前窗口最大值。

为什么可行：

• 队列保持递减，所以队首是当前窗口最大值的候选。
• 及时移除过期元素和不可能成为最大值的元素，保持队列简洁。

4. 详细步骤演示（示例 1）

nums = [1,3,-1,-3,5,3,6,7], k = 3

初始化队列 deque，结果列表 res = []。

i=0 (值=1)
队列空 → 加入索引 0。
队列: [0] (对应值 [1])
窗口未形成，不记录最大值。

i=1 (值=3)
从队尾比较：1 < 3 → 弹出索引 0。
队列空 → 加入索引 1。
队列: [1] (对应值 [3])
窗口未形成。

i=2 (值=-1)
从队尾比较：3 > -1 → 直接加入索引 2。
队列: [1,2] (对应值 [3, -1])
窗口形成，res.append(nums[1]=3) → res=[3]

i=3 (值=-3)
队首索引 1 在窗口内（左边界 i-k+1=1，索引1>=1，未过期）。
从队尾比较：-1 > -3 → 加入索引 3。
队列: [1,2,3] (对应值 [3,-1,-3])
队首值 3，res=[3,3]

i=4 (值=5)
队首索引 1 已不在窗口（左边界=2，索引1<2 → 过期），弹出队首 → 队列 [2,3]
从队尾比较：-3 < 5 → 弹出索引 3；-1 < 5 → 弹出索引 2；队列空 → 加入索引 4。
队列: [4] (对应值 [5])
队首值 5，res=[3,3,5]

i=5 (值=3)
队首索引 4 在窗口内（左边界=3，索引4>=3）。
从队尾比较：5 > 3 → 加入索引 5。
队列: [4,5] (对应值 [5,3])
队首值 5，res=[3,3,5,5]

i=6 (值=6)
队首索引 4 在窗口内（左边界=4，索引4>=4）。
从队尾比较：3 < 6 → 弹出索引 5；5 < 6 → 弹出索引 4；队列空 → 加入索引 6。
队列: [6] (对应值 [6])
队首值 6，res=[3,3,5,5,6]

i=7 (值=7)
队首索引 6 在窗口内（左边界=5，索引6>=5）。
从队尾比较：6 < 7 → 弹出索引 6；队列空 → 加入索引 7。
队列: [7] (对应值 [7])
队首值 7，res=[3,3,5,5,6,7]

最终结果: [3,3,5,5,6,7]

5. 代码实现（Python）

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()
    res = []
    for i in range(len(nums)):
        # 移除超出窗口的队首元素
        if dq and dq[0] == i - k:
            dq.popleft()
        # 维护队列单调递减：从队尾移除比当前元素小的
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)
        # 当窗口大小达到k时，记录最大值
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

6. 复杂度分析

• 时间复杂度：O(n)，每个元素最多入队一次、出队一次。
• 空间复杂度：O(k)，队列最多存储 k 个元素。

7. 总结

• 单调队列是高效解决滑动窗口最大值/最小值问题的利器。
• 核心是保持队列单调性，并及时移除过期元素。
• 相比堆解法，单调队列将复杂度从 O(n log n) 优化到 O(n)。

这样一步步从暴力法到最优解，你应该能清晰理解这个题目的解决思路了。