単調スタック

01 / 一文で言うと

値が単調に保たれるスタックを維持する —— 次の要素が順序を破るたびに、ポップされる要素は まさに「現在の要素が答えとなる」要素である。
問題添字ごとの次に大きい要素入力[2, 1, 2, 4, 3, 1]
入力
20
11
22
43
34
15
スタック →
— 空 —
結果
?0
?1
?2
?3
?4
?5
左から右へ走査する。値が下から上へ厳密に減少する添字のスタックを保つ。
ステップ
0 / 23
i
—
スタック長
0
結果の充填
0 / 6
0 / 23

02 / パターンの骨格

# 次に大きい要素 —— 厳密減少のスタックstack ← [ ]for i in 0..n−1:while stack が空でなく かつ arr[stack.top] < arr[i]:j ← stack.pop()result[j] ← arr[i] // i が j の次に大きい要素stack.push(i)# スタックに残った要素は右側に大きい要素がない → result ← −1

03 / このパターンを使うべき合図

「次に大きい / 小さい」
各要素について、その右(または左)で最も近い大きい(または小さい)要素を求める。 このパターンは違反者が現れた瞬間に、その添字の答えを出力する。
「各要素について…を求めよ」
答えは添字ごと、集約値ではない ——そして関係は位置に基づくものであり、値そのものに基づくものではない。
「ヒストグラム / span」
最大長方形、雨水捕集、株価スパン —— いずれも、最も近い大きい / 小さい近傍が境界を定める問題。
「O(n)」
目標計算量からして、添字ごとに O(N²) の素朴な走査は除外され、 償却 1 パスのアプローチが暗示されている。

04 / よくある落とし穴

値ではなく添字を積むべきところを取り違える。
ポップ時にはほぼ必ず result[j] に書き込むので、スタックは 各ポップ要素がどこから来たかを覚えていなければならない。 添字を積み、値は arr[stack.top] で参照する。
内側 while における < と ≤。
厳密(<)は「厳密に次に大きい」—— 同値はより大きいものが来るまでスタックに残る。 非厳密(≤)は「次に同じか大きい」—— 同値もポップされ、互いに答えを記録する。 これらは別問題であり、選択が同値ケースの結果を静かに変えてしまう。
末尾の残りを忘れる。
ループ終了時にスタックに残っている添字には、右側に「より大きい要素が存在しない」。 結果を -1 に初期化する(あるいは仕様に応じてスキップする)。 見落としやすい部分だ。

05 / LeetCode で練習

簡単4

01Valid Parentheses— LC 20→02Next Greater Element I— LC 496→03Final Prices With a Special Discount in a Shop— LC 1475→04Maximum Nesting Depth of the Parentheses— LC 1614→

中級23

01Container With Most Water— LC 11→02Remove Duplicate Letters— LC 316→03Remove K Digits— LC 402→04132 Pattern— LC 456→05Next Greater Element II— LC 503→06Asteroid Collision— LC 735→07Daily Temperatures— LC 739→08Score of Parentheses— LC 856→09Online Stock Span— LC 901→10Sum of Subarray Minimums— LC 907→11Minimum Add to Make Parentheses Valid— LC 921→12Validate Stack Sequences— LC 946→13Check If Word Is Valid After Substitutions— LC 1003→14Next Greater Node In Linked List— LC 1019→15Smallest Subsequence of Distinct Characters— LC 1081→16Reverse Substrings Between Each Pair of Parentheses— LC 1190→17Minimum Remove to Make Valid Parentheses— LC 1249→18Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit— LC 1438→19Find the Most Competitive Subsequence— LC 1673→20Jump Game VI— LC 1696→21Maximum Subarray Min-Product— LC 1856→22Sum of Subarray Ranges— LC 2104→23Check if a Parentheses String Can Be Valid— LC 2116→

難しい9

01Longest Valid Parentheses— LC 32→02Trapping Rain Water— LC 42→03Largest Rectangle in Histogram— LC 84→04Maximal Rectangle— LC 85→05Sliding Window Maximum— LC 239→06Trapping Rain Water II— LC 407→07Shortest Subarray with Sum at Least K— LC 862→08Maximum Number of Robots Within Budget— LC 2398→09Next Greater Element IV— LC 2454→