单调队列

What · 是什么

单调队列(Monotonic Queue)是一个双端队列(deque)，在队尾插入元素时弹出所有破坏单调性的元素，使队列内元素保持单调递增或递减。同时通过记录元素位置来淘汰超出窗口范围的队首。可在 O(n) 均摊时间内维护滑动窗口的最值，是 DP 优化(如多重背包、斜率优化)的基础。

Why · 为什么

How · 实现

伪代码

# 滑动窗口最大值 (窗口大小 k)
dq = deque()  # 存下标, 维护递减
for i in range(n):
  # 1. 弹出超出窗口的队首
  while dq and dq[0] < i - k + 1:
    dq.popleft()
  # 2. 弹出不满足单调性的队尾
  while dq and arr[dq[-1]] <= arr[i]:
    dq.pop()
  # 3. 入队
  dq.append(i)
  # 4. 记录答案(i >= k-1 时)
  if i >= k - 1:
    ans.append(arr[dq[0]])

Python 实现

from collections import deque

def sliding_window_max(arr, k):
    """滑动窗口最大值: 返回每个窗口的最大值。
    单调递减队列(存下标)。
    LeetCode 239 模板。
    """
    n = len(arr)
    if n == 0:
        return []
    dq = deque()  # 存下标, arr[dq[i]] 递减
    ans = []
    for i in range(n):
        # 弹出超出窗口的队首
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # 弹出比当前元素小的队尾(它们不可能成为最大值)
        while dq and arr[dq[-1]] <= arr[i]:
            dq.pop()
        dq.append(i)
        # 第一个窗口完整后开始记录
        if i >= k - 1:
            ans.append(arr[dq[0]])
    return ans


def sliding_window_min(arr, k):
    """滑动窗口最小值: 单调递增队列。"""
    n = len(arr)
    if n == 0:
        return []
    dq = deque()  # 存下标, arr[dq[i]] 递增
    ans = []
    for i in range(n):
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        while dq and arr[dq[-1]] >= arr[i]:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            ans.append(arr[dq[0]])
    return ans


def dp_sliding_window_max(arr, k):
    """DP优化示例: dp[i] = max(arr[i-k..i]) 的递推。
    用单调队列优化到 O(n)。
    """
    n = len(arr)
    if n == 0:
        return []
    dp = [0] * n
    dq = deque()
    for i in range(n):
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        while dq and arr[dq[-1]] <= arr[i]:
            dq.pop()
        dq.append(i)
        dp[i] = arr[dq[0]]
    return dp


if __name__ == '__main__':
    arr = [1, 3, -1, -3, 5, 3, 6, 7]
    k = 3

    # 测试滑动窗口最大值
    maxs = sliding_window_max(arr, k)
    print(f'Window max: {maxs}')
    assert maxs == [3, 3, 5, 5, 6, 7]

    # 测试滑动窗口最小值
    mins = sliding_window_min(arr, k)
    print(f'Window min: {mins}')
    assert mins == [-1, -3, -3, -3, 3, 3]

    # 测试DP优化
    dp = dp_sliding_window_max(arr, k)
    print(f'DP max:     {dp}')

    print('All monotonic queue tests passed!')

易错点

• 队首弹出条件用 dq[0] < i-k+1(下标比较) 而非值比较，存的是下标不是值
• 求最大值用递减队列(弹出<=当前的), 求最小值用递增队列(弹出>=当前的), 方向搞反会错
• 弹出队尾用 pop()(从尾部), 弹出队首用 popleft()(从头部), 不能混用
• 第一个完整窗口在 i=k-1 时形成, 之前不应记录答案

例题

信源

• OI Wiki✓ https://oi-wiki.org/ds/monotonic-queue/
• CP-Algorithms✓ https://cp-algorithms.com/data_structures/stack_queue_modification.html