単調両端キュー
01 / 一文で言うと
値が先頭から末尾へ単調に保たれる両端キュー。両端は別の役を持つ:先頭は窓が過ぎた添字をポップし、末尾は新しい値に支配された添字を落とす。 先頭は常に窓最大値の添字 —— O(1) で読める。
問題スライディングウィンドウの最大値 —— 窓 1 つにつき 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) に縮める。
「窓ごとに 1 値」
出力は窓ごとに 1 つの値 —— 単調スタックの「添字ごとに 1 値」の対偶。 窓位置で番号付けされるだけ。
「最短部分配列…」
多くの「ある条件を満たす最短部分配列」問題(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
難しい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→