30 秒速览

  • 队列：FIFO，适合 BFS、层序遍历
  • 单调队列：维护滑动窗口最值，O(n)
  • 堆：动态维护最值，插入/删除 O(log n)

一、队列

直觉建立

想象排队买票：

  • 先来的人先买（FIFO）
  • 队头出队，队尾入队

队列的核心价值：按顺序处理，适合 BFS。

Python 中的队列

from collections import deque

# 双端队列
q = deque()
q.append(1)        # 右边入队
q.appendleft(0)    # 左边入队
q.pop()            # 右边出队
q.popleft()        # 左边出队（普通队列用这个）

二、单调队列

什么是单调队列？

队列中元素保持单调递增或单调递减。

单调递减队列：队头是最大值，用于求滑动窗口最大值。 单调递增队列：队头是最小值，用于求滑动窗口最小值。

例题 1：LC 239. 滑动窗口最大值

题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。返回滑动窗口中的最大值。

示例：

输入: nums = [1,3,-1,-3,5,3,6,7], k = 3
输出: [3,3,5,5,6,7]

思路

维护单调递减双端队列：

  • 队首是当前窗口最大值
  • 新元素进来时，从队尾移除所有小于它的元素
  • 队首元素出窗口时，从队首移除
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

i=0 (1): queue = [0]
i=1 (3): 3 > 1, 移除 0, queue = [1]
i=2 (-1): queue = [1, 2], 输出 nums[1]=3

i=3 (-3): queue = [1, 2, 3], 输出 nums[1]=3
i=4 (5): 5 > -3,-1,3, 全部移除, queue = [4], 输出 nums[4]=5
i=5 (3): queue = [4, 5], 输出 nums[4]=5
i=6 (6): 6 > 3,5, 全部移除, queue = [6], 输出 nums[6]=6
i=7 (7): 7 > 6, 移除 6, queue = [7], 输出 nums[7]=7

代码

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    queue = deque()  # 存储索引，保持单调递减
    result = []

    for i in range(len(nums)):
        # 移除窗口外的元素
        while queue and queue[0] < i - k + 1:
            queue.popleft()

        # 移除所有小于当前元素的元素（维护单调性）
        while queue and nums[queue[-1]] < nums[i]:
            queue.pop()

        queue.append(i)

        # 窗口形成后，输出最大值
        if i >= k - 1:
            result.append(nums[queue[0]])

    return result

复杂度：时间 O(n)，空间 O(k)

例题 2：LC 862. 和至少为 K 的最短子数组

题目：返回 A 中最短的非空连续子数组的长度，该子数组的和至少为 K。如果没有则返回 -1。

思路

  1. 计算前缀和
  2. 用单调队列维护可能的最优起点
  3. 对于每个位置，找到最远的满足条件的起点
from collections import deque

def shortestSubarray(nums: list[int], k: int) -> int:
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    result = n + 1
    queue = deque()  # 单调递增队列，存储前缀和索引

    for i in range(n + 1):
        # 尝试找到满足条件的子数组
        while queue and prefix[i] - prefix[queue[0]] >= k:
            result = min(result, i - queue.popleft())

        # 维护单调性
        while queue and prefix[i] <= prefix[queue[-1]]:
            queue.pop()

        queue.append(i)

    return result if result <= n else -1

复杂度：时间 O(n)，空间 O(n)

三、堆（优先队列）

什么是堆？

堆是一棵完全二叉树，满足堆性质：

  • 大顶堆：父节点 >= 子节点，堆顶是最大值
  • 小顶堆：父节点 <= 子节点，堆顶是最小值

Python 中的堆

Python 的 heapq 是小顶堆。

import heapq

# 小顶堆
heap = []
heapq.heappush(heap, 3)    # 插入
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappop(heap)        # 弹出最小值 1

# 大顶堆（取负数）
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappop(max_heap)    # 弹出 -(-3) = 3

# 堆化
arr = [3, 1, 2]
heapq.heapify(arr)         # O(n) 堆化

堆的操作复杂度

操作时间复杂度
插入O(log n)
删除堆顶O(log n)
获取堆顶O(1)
堆化O(n)

例题 3：LC 215. 数组中的第 K 个最大元素

题目：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

思路一：小顶堆

维护大小为 k 的小顶堆，堆顶就是第 k 大的元素。

import heapq

def findKthLargest(nums: list[int], k: int) -> int:
    heap = []

    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)

    return heap[0]

复杂度：时间 O(n log k)，空间 O(k)

思路二：快速选择

def findKthLargest(nums: list[int], k: int) -> int:
    def partition(left, right):
        pivot = nums[right]
        i = left
        for j in range(left, right):
            if nums[j] > pivot:  # 降序排列
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[right] = nums[right], nums[i]
        return i

    left, right = 0, len(nums) - 1
    while True:
        pos = partition(left, right)
        if pos == k - 1:
            return nums[pos]
        elif pos < k - 1:
            left = pos + 1
        else:
            right = pos - 1

复杂度：平均 O(n)，最坏 O(n²)

例题 4：LC 347. 前 K 个高频元素

题目：给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。

代码

import heapq
from collections import Counter

def topKFrequent(nums: list[int], k: int) -> list[int]:
    # 统计频率
    count = Counter(nums)

    # 用堆找前 k 个
    # 堆元素：(频率, 数值)
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)

    return [num for freq, num in heap]

复杂度：时间 O(n log k)，空间 O(n)

例题 5：LC 295. 数据流的中位数

题目：中位数是有序序列最中间的那个数。设计一个支持以下两种操作的数据结构：

  • addNum(num)：添加一个数
  • findMedian()：返回当前所有数的中位数

思路：对顶堆

用两个堆维护数据：

  • 大顶堆 small：存储较小的一半
  • 小顶堆 large：存储较大的一半

保持 len(small) == len(large) 或 len(small) == len(large) + 1。

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # 大顶堆（存储负数模拟）
        self.large = []  # 小顶堆

    def addNum(self, num: int) -> None:
        # 先加入 small
        heapq.heappush(self.small, -num)

        # 把 small 最大值移到 large
        heapq.heappush(self.large, -heapq.heappop(self.small))

        # 平衡：如果 large 多了，移回 small
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

复杂度：addNum O(log n)，findMedian O(1)

例题 6：LC 23. 合并 K 个升序链表

题目：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

思路

用小顶堆维护所有链表的当前最小值。

import heapq

def mergeKLists(lists: list) -> ListNode:
    # 堆元素：(值, 链表索引, 节点)
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode(0)
    cur = dummy

    while heap:
        val, i, node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next

        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

复杂度：时间 O(n log k)，空间 O(k)

四、BFS 队列

例题 7：LC 102. 二叉树的层序遍历

题目：给你二叉树的根节点 root，返回其节点值的层序遍历。

代码

from collections import deque

def levelOrder(root: TreeNode) -> list[list[int]]:
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

复杂度：时间 O(n)，空间 O(n)

例题 8：LC 200. 岛屿数量

题目：给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

BFS 代码

from collections import deque

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    count = 0

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                # BFS 标记整个岛屿
                queue = deque([(i, j)])
                grid[i][j] = '0'

                while queue:
                    x, y = queue.popleft()
                    for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
                            grid[nx][ny] = '0'
                            queue.append((nx, ny))

    return count

复杂度：时间 O(mn)，空间 O(min(m,n))

五、复盘清单

触发信号

数据结构触发信号
队列BFS、层序遍历、按顺序处理
单调队列滑动窗口最值
堆动态维护最值、Top K、合并有序流
对顶堆动态中位数

边界条件

  • 空输入
  • k = 1 或 k = n
  • 堆为空时获取堆顶

常见错误

  • Python heapq 是小顶堆，大顶堆要取负
  • 单调队列忘记移除窗口外元素
  • BFS 忘记标记已访问

六、题目清单

队列

题号题目难度考点
102二叉树的层序遍历MediumBFS 队列
200岛屿数量MediumBFS
54201 矩阵MediumBFS

单调队列

题号题目难度考点
239滑动窗口最大值Hard单调队列
862和至少为 K 的最短子数组Hard单调队列

堆

题号题目难度考点
215数组中的第 K 个最大元素Medium小顶堆
347前 K 个高频元素Medium小顶堆
295数据流的中位数Hard对顶堆
23合并 K 个升序链表Hard小顶堆
703. 数据流中的第 K 大元素Easy小顶堆