力扣百题通

239. 滑动窗口最大值 (Hard)

Properties2
description给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。
tags02-双指针与滑动窗口, 05-单调栈

12分钟阅读

239. 滑动窗口最大值 (Hard)

专题归类： 02-双指针与滑动窗口 · 05-单调栈 LeetCode 链接： https://leetcode.cn/problems/sliding-window-maximum/

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

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

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

示例：

输入：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

补充说明：

  • 数组长度范围：1 <= nums.length <= 10^5
  • k 的范围：1 <= k <= nums.length
  • 数值范围：-10^4 <= nums[i] <= 10^4

题目详细分析

数据范围含义：

  • n 最大 10^5，k 最大等于 n。暴力法（对每个窗口遍历 k 个元素找最大）是 O(n×k)，最坏 O(10
  • 数值范围较小（±10
  • 需要 O(n) 或 O(n log k) 的解法。

核心要求：

  • 对每个窗口（共 n - k + 1 个窗口）输出最大值。
  • 窗口每次只移动 1 位——相邻窗口之间有 k-1 个元素是重叠的，可以利用这个重叠来优化。

边界条件：

  • k = 1：每个元素自身就是最大值，结果就是 nums 本身。
  • k = n：只有一个窗口，结果就是整个数组的最大值。
  • 数组可能包含负数，不影响算法（比较大小不依赖正负）。

隐藏条件：

  • 窗口滑动的本质是”先进先出”（FIFO）+“实时最大值”。需要一种数据结构，能在 O(1) 时间获取当前窗口的最大值，并且在删除过期元素、添加新元素后也能快速更新。
  • 最大堆（优先队列）可以 O(log k) 获取最大值并更新，但 O(1) 需要更巧妙的数据结构——单调队列。
  • 关键在于：当新元素很大时，窗口中比它小的”旧”元素永远不可能再成为最大值了（因为新元素更大且更晚过期），可以直接丢弃。

小白版直白理解

想象你在看一排数字，你有一个固定大小的”取景框”（窗口），从左边滑到右边。每次滑动后，你要说出框里最大的数字。

笨办法： 每次框停住后，你扫一遍框里的所有数字，找出最大的。框移动 n-k+1 次，每次看 k 个数字，加起来就是 n×k 次。

聪明办法（单调队列）： 你准备一个”候选名单”（双端队列），规则是：

  1. 新来的数字如果比名单里最后的数字大，就把最后那个删掉（因为最后那个已经没机会当老大了）。
  2. 重复第 1 步，直到名单末尾的数字比新来的大，或者名单空了。然后把新来的加到末尾。
  3. 如果名单最前面的数字已经”滑出窗口”了，就把它从前面移除。
  4. 每次名单最前面的数字就是当前窗口的最大值。

这样每个数字最多进一次名单、出一次名单，非常高效！

解题思路

思路一：单调队列（推荐）

核心想法： 维护一个双端队列 q，队列中存储元素的索引（不是值），且这些索引对应的值在队列中是单调递减的。

为什么存储索引而不是值？ 因为我们需要判断队首元素是否已经滑出窗口——这需要通过索引与 i - k + 1 的关系来判断。

关键洞察： 当新元素 nums[i] 加入时，队列中所有比 nums[i] 小的元素都失去了成为最大值的可能（它们更早过期，更小），可以直接从队尾弹出。

单调队列的维护三步走：

  1. 维护单调性：从队尾弹出所有比 nums[i] 小的索引。
  2. 入队：将当前索引 i 加入队尾。
  3. 移除过期：如果队首索引 q[0] 已经不在窗口内（q[0] <= i - k），从队首弹出。
  4. 记录结果：当窗口形成（i >= k - 1）后，队首索引对应的值就是当前窗口最大值。
from collections import deque
 
def maxSlidingWindow(nums, k):
    """
    单调递减队列
    队列中存储元素索引，对应的值从大到小排列
    
    步骤：
    1. 弹出队尾比当前小的元素（它们再也没机会成最大值了）
    2. 将当前元素索引加入队尾
    3. 弹出队首过期元素（索引超出窗口）
    4. 窗口形成后，队首即最大值
    """
    q = deque()  # 存储元素索引，单调递减
    res = []
    
    for i, num in enumerate(nums):
        # 1. 维护单调性：弹出队尾所有比当前元素小的索引
        while q and nums[q[-1]] < num:
            q.pop()
        
        # 2. 当前元素索引入队
        q.append(i)
        
        # 3. 移除过期元素：队首索引超出窗口左边界
        if q[0] <= i - k:
            q.popleft()
        
        # 4. 窗口形成后记录结果（前 k-1 个元素不够一个窗口）
        if i >= k - 1:
            res.append(nums[q[0]])
    
    return res

思路二：优先队列（最大堆）

核心想法： 用最大堆存储窗口内元素，同时记录索引以判断过期。每次从堆顶取最大值，如果最大值已经过期则弹出，直到找到有效的最大值。

虽然直观，但时间复杂度 O(n log k)，且堆的常数比单调队列大。

import heapq
 
def maxSlidingWindow_heap(nums, k):
    """
    最大堆解法
    堆中存储 (-value, index)，利用 Python 的 heapq（最小堆）模拟最大堆
    """
    heap = []
    res = []
    
    for i, num in enumerate(nums):
        heapq.heappush(heap, (-num, i))
        
        if i >= k - 1:
            # 移除过期堆顶（索引超出窗口左边界）
            while heap and heap[0][1] <= i - k:
                heapq.heappop(heap)
            res.append(-heap[0][0])
    
    return res

思路三：暴力法（不推荐，理解用）

对每个窗口，遍历 k 个元素找最大值。O(n×k)，超时。

def maxSlidingWindow_brute(nums, k):
    """暴力法 O(n×k)，会超时"""
    res = []
    for i in range(len(nums) - k + 1):
        res.append(max(nums[i:i + k]))
    return res

易错点

  • 存储索引而非值： 队列中存储的必须是索引而不是值。因为我们需要判断过期——值无法告诉我们元素是否还在窗口内，只有索引可以。
  • 单调性定义： 是单调递减（从大到小），队首是最大值。不是单调递增。如果是递增，队首是最小值，不符合需求。
  • 出队顺序： 先弹出队尾小元素，再加入新元素，再弹出队首过期元素，最后取结果。顺序不要搞反。特别是，新加入的元素可能在下一步就变成过期的（虽然不可能，因为 i 刚被加入，i - k 至少比 i 小 k），但逻辑顺序仍然要正确。
  • 过期判断条件： q[0] <= i - k，不是 q[0] < i - k + 1。两者等价但前者更简洁。注意当 q[0] == i - k 时，它已经在窗口的左边界之外了（窗口是左闭右闭 [i-k+1, i]）。
  • 窗口未形成时不记录： i >= k - 1 时才记录结果。前 k-1 个元素还没构成完整的窗口。
  • 空队列检查： while 操作队列前需要检查是否为空。
  • Python 的 heapq 是最小堆： 用 (-value, index) 来模拟最大堆。

框架提炼

单调队列模板：

单调队列是一种特殊的数据结构，用于维护滑动窗口中的最值（最大值或最小值）。核心是”没机会的元素及时丢弃”。

from collections import deque
 
def monotonic_queue(nums, k):
    """
    单调递减队列通用模板
    用于维护滑动窗口最大值
    """
    q = deque()
    res = []
    
    for i, num in enumerate(nums):
        # 1. 维护单调性
        while q and nums[q[-1]] < num:  # 递减：求最大值用 <
            q.pop()                      # 递增：求最小值用 >
        
        # 2. 入队
        q.append(i)
        
        # 3. 移除过期
        if q[0] < i - k + 1:  # 或 q[0] <= i - k
            q.popleft()
        
        # 4. 记录结果
        if i >= k - 1:
            res.append(nums[q[0]])
    
    return res

单调队列 vs 优先队列：

特性单调队列优先队列（堆）
获取最值O(1)O(1)
更新O(1) 摊销O(log n)
过期元素处理O(1) 惰性移除O(log n) 惰性移除
实现复杂度稍复杂简单（调 API）
适用场景滑动窗口最值全局动态最值

使用原则：当窗口大小固定且滑动时，单调队列是最高效的。

关联题目

关系图谱