单调双端队列

01 / 一句话本质

值从队首到队尾保持单调的双端队列,两端各司其职:队首负责在窗口滑过时弹出过期的下标;队尾负责在新值到来时弹出被压制的下标。 队首始终是当前窗口最大值的下标 —— O(1) 取到。
题目滑动窗口最大值 —— 每个窗口一个值输入[1, 3, -1, -3, 5, 3, 6, 7], k=3
输入
10
31
-12
-33
54
35
66
77
双端队列 ↔
— 空 —
结果
?0
?1
?2
?3
?4
?5
用大小为 k = 3 的窗口在数组上滑动。维护一个下标双端队列,值从队首到队尾严格递减 —— 队首始终是当前窗口的最大值。
步
0 / 39
i
—
队列大小
0
已记录窗口
0 / 6
0 / 39

02 / 模式骨架

# 滑动窗口最大值 —— 严格递减的下标双端队列dq ← [ ] // 下标的双端队列for i in 0..n−1:if dq 非空 且 dq.front ≤ i − k:dq.popFront() // 已滑出窗口while dq 非空 且 arr[dq.back] < arr[i]:dq.popBack() // 被压制,不会成为未来窗口最大值dq.pushBack(i)if i ≥ k − 1: result[i − k + 1] ← arr[dq.front]

03 / 什么时候用这个模式

"每个窗口的最大值 / 最小值"
凡是"对每个长度为 k 的连续窗口求最大值(或最小值)"的题面 —— 标准型。 朴素扫描是 O(N·k);单调双端队列把它降到 O(N)。
"每个窗口一个答案"
输出是每个窗口一个值 —— 形态与单调栈的"每个下标一个值"对偶, 只是改为按窗口位置编号。
"使..的最短子数组"
很多"使某个条件成立的最短子数组"问题(LC 862、1425、1499) 都归约为对前缀和或 DP 值维护一个单调双端队列。
"O(N)"
与单调栈同源 —— 朴素的每窗口内循环被排除。 若子例程需要 O(1) 取"窗口内最大值",就是这个模式。

04 / 常见坑

两端的工作搞混。
双端队列两端各干各的:时间(队首,窗口滑过时弹出)与价值(队尾,被新值压制时弹出)。看起来对称但条件不同: 队首用 dq.front ≤ i − k,队尾用 arr[dq.back] < arr[i]。 搞反会得到错误答案,而且静默。
存值而不是下标。
需要知道队首值何时进入窗口才能弹出。 存下标,值通过 arr[dq.front] 查表得到。
队尾弹出条件 < 与 ≤。
严格(<)在队列里保留相等下标 —— 正确,但略浪费空间。 非严格(≤)连相等也弹出。对滑动窗口最大值两者都对; 若要"以最新下标为最大值",用 ≤ 更直接。
窗口未满时就开始记录。
前 k − 1 次迭代窗口还没填满 —— 此时记录会得到错误长度的输出。 用 if i ≥ k − 1 守卫。

05 / 去 LeetCode 上练习

中等7

01Min Stack— LC 155→02Sum of Subarray Minimums— LC 907→03Grumpy Bookstore Owner— LC 1052→04Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit— LC 1438→05Jump Game VI— LC 1696→06Maximum Subarray Min-Product— LC 1856→07Maximum Tastiness of Candy Basket— LC 2517→

困难11

01Largest Rectangle in Histogram— LC 84→02Maximal Rectangle— LC 85→03Sliding Window Maximum— LC 239→04Max Stack— LC 716→05Shortest Subarray with Sum at Least K— LC 862→06Subarrays with K Different Integers— LC 992→07Minimum Number of K Consecutive Bit Flips— LC 995→08Constrained Subsequence Sum— LC 1425→09Max Value of Equation— LC 1499→10Number of Visible People in a Queue— LC 1944→11Maximum Number of Robots Within Budget— LC 2398→