好的，我们这次来详细讲解 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 时会超时。
• 所以必须找到 O(n) 或 O(n log k) 的算法。

3. 思路演进

3.1 暴力法（不可行）

对每个窗口扫描 k 个元素找最大值：

def maxSlidingWindow(nums, k):
    n = len(nums)
    if n * k == 0:
        return []
    return [max(nums[i:i+k]) for i in range(n - k + 1)]

• 时间复杂度：O(n*k)，在 n 和 k 都很大时超时。
• 空间复杂度：O(1)（除了输出数组）。

3.2 使用大根堆（优先队列）

我们可以用一个最大堆（Python 中用负值模拟最大堆）来维护窗口内的元素，堆顶就是最大值。

但问题：当窗口滑动时，需要删除左边出去的元素，而堆的删除非堆顶元素需要 O(k) 时间（先找到再删，再调整堆），或者用延迟删除技巧。

延迟删除思路：

• 用最大堆存储 (数值, 索引)。
• 每次取堆顶时，如果堆顶元素的索引不在当前窗口范围内，说明是之前该删但没删的，就 pop 掉，直到堆顶元素在当前窗口内。
• 这样每个元素入堆一次、出堆一次，时间复杂度 O(n log n)。

import heapq

def maxSlidingWindow(nums, k):
    n = len(nums)
    # 最大堆：(-值, 索引)
    heap = []
    res = []
    for i in range(n):
        heapq.heappush(heap, (-nums[i], i))
        if i >= k - 1:
            # 删除堆顶中索引小于等于 i-k 的（不在窗口）
            while heap[0][1] <= i - k:
                heapq.heappop(heap)
            res.append(-heap[0][0])
    return res

• 时间复杂度：最坏 O(n log n)，因为可能堆里积压很多过期元素，但每次只删一个堆顶。
• 可以优化：但延迟删除在极端情况下堆大小是 O(n)，不是 O(k)。

3.3 最优解：单调队列（Deque 方法）

我们希望维护一个队列，能在 O(1) 时间内获得当前窗口的最大值，并且在窗口滑动时快速更新。

核心思想：

• 队列中存储数组的索引，而不是值。
• 队列对应元素的值从队首到队尾是单调递减的（这样队首就是当前窗口的最大值）。
• 在窗口滑动过程中：
  1. 移除队首过期索引（如果队首索引等于 i-k，说明该索引已不在窗口内，出队）。
  2. 从队尾开始，删除所有小于等于当前新元素 nums[i] 的索引（因为它们不可能是窗口最大值了），保持单调递减。
  3. 将当前索引入队尾。
  4. 当窗口形成后（i >= k-1），记录队首对应的值作为窗口最大值。

4. 逐步推演示例

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

初始化：双端队列 deque，结果列表 res = []

i=0, num=1

• 队列空，直接加入索引 0 → deque = [0]（对应值 [1]）
• 窗口未形成，不记录最大值。

i=1, num=3

• 队尾对应值 nums[0]=1 < 3，弹出队尾 → deque 空 → 加入索引 1 → deque = [1]（值 [3]）
• 窗口未形成。

i=2, num=-1

• 队尾对应值 nums[1]=3 > -1，直接加入索引 2 → deque = [1,2]（值 [3,-1]）
• 窗口形成 [1,3,-1]，队首索引 1 在窗口内，最大值 nums[1]=3 → res = [3]

i=3, num=-3

• 队首索引 1 不在过期范围（i-k=0，索引 1>0，未过期）
• 队尾对应值 nums[2]=-1 > -3，加入索引 3 → deque = [1,2,3]（值 [3,-1,-3]）
• 窗口 [3,-1,-3]，最大值 nums[1]=3 → res = [3,3]

i=4, num=5

• 队首索引 1 过期？i-k=1，索引 1 ≤ 1，过期 → 弹出队首 → deque = [2,3]
• 队尾值 nums[3]=-3 < 5，弹出队尾 → deque = [2]
• 队尾值 nums[2]=-1 < 5，弹出队尾 → deque 空 → 加入索引 4 → deque = [4]（值 [5]）
• 窗口 [-1,-3,5]，最大值 5 → res = [3,3,5]

i=5, num=3

• 队首索引 4 未过期（i-k=2，4>2）
• 队尾值 nums[4]=5 > 3，加入索引 5 → deque = [4,5]（值 [5,3]）
• 窗口 [-3,5,3]，最大值 nums[4]=5 → res = [3,3,5,5]

i=6, num=6

• 队首索引 4 未过期（i-k=3，4>3）
• 队尾值 nums[5]=3 < 6，弹出队尾 → deque = [4]
• 队尾值 nums[4]=5 < 6，弹出队尾 → deque 空 → 加入索引 6 → deque = [6]（值 [6]）
• 窗口 [5,3,6]，最大值 6 → res = [3,3,5,5,6]

i=7, num=7

• 队首索引 6 未过期（i-k=4，6>4）
• 队尾值 nums[6]=6 < 7，弹出队尾 → deque 空 → 加入索引 7 → deque = [7]（值 [7]）
• 窗口 [3,6,7]，最大值 7 → res = [3,3,5,5,6,7]

5. 代码实现（Python）

from collections import deque

def maxSlidingWindow(nums, k):
    n = len(nums)
    if n == 0 or k == 0:
        return []
    if k == 1:
        return nums
    
    dq = deque()  # 存储索引
    res = []
    
    for i in range(n):
        # 1. 移除超出窗口的队首元素
        if dq and dq[0] == i - k:
            dq.popleft()
        
        # 2. 从队尾移除小于当前值的元素
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        # 3. 当前索引入队尾
        dq.append(i)
        
        # 4. 记录窗口最大值（当窗口形成后）
        if i >= k - 1:
            res.append(nums[dq[0]])
    
    return res

6. 复杂度分析

• 时间复杂度：O(n)
  每个元素最多入队一次、出队一次，所以均摊 O(1) 每个元素，总共 O(n)。

• 空间复杂度：O(k)
  双端队列最多存储 k 个索引。

7. 关键点总结

• 单调队列保持索引对应值递减，队首是当前窗口最大值。
• 队尾插入前要“踢掉”比自己小的元素，因为它们不再可能成为最大值。
• 检查队首是否过期用索引判断：dq[0] == i - k 时出队。
• 窗口形成条件：i >= k-1 时开始记录结果。

这样就能高效解决滑动窗口最大值问题。