こんにちは、普段はLeetCode Weekly Contestに参加している、imotyと申します。この大会は毎週日曜日の11:30-13:00(JST)に開催され、簡単な問題も含め全４問です。対応言語も多く、また標準入力のパースもないです。楽しいので日曜日に大会出たいとき是非どうぞ。
本記事ではMonotonic Stack(単調スタック)というデータ構造の解説と、発展形の紹介をします。
Monotonic Stackは、競技プログラミングで典型問題の一つだと考えています。その場ですぐ思いつく難易度は高いので、典型問題を練習しておく価値があります。さらに、同じく思いつくのが難しい発展形もあります。発展形も頭の片隅に入れておくことで、解ける問題が増えることでしょう。
本記事では、まずはじめにMonotonic Stackの解説をし、その後に発展形の紹介をします。
Monotonic Stack の解説
Monotonic Stack（単調スタック）は、ある「運用上の縛り」を加えた、ただのスタックです。その「縛り」とは、スタックの要素が、常に単調増加または単調減少になるようにするのです。
Monotonicという英単語は、単調と訳され、用例には、単調増加(monotonic increasing)、単調減少(monotonic decreasing)などがあります。
基本原理
基本原理は、スタックを常に単調増加(または単調減少)に保つ、ということです。
要素を追加する場合、必要であればポップします。
以降、スタックを単調増加を保つとき、ひとつ要素を追加するケースを考えましょう。
- 追加したい要素が、スタックの末尾の要素より大きい場合
- そのまま追加します。
- この操作によっても、スタックの単調増加は保たれています。
- 追加したい要素が、スタックの末尾の要素より小さい場合
- スタックの末尾が追加したい要素より大きいとき、これをポップします
- これを、必要なだけ繰り返します
この要素追加時のこの操作によって、スタックを単調増加に保つことができます。
単調減少に保つ場合も同様の処理を行うことができます。
実装例
ここで典型例として、配列をスタックとして使う、単調増加な Monotonic Stackの実装例をあげます。
def monotonic_increasing_stack(nums):
stack = []
result = []
for num in range(nums):
while stack and stack[-1] > num:
stack.pop()
stack.append(nums[i])
result.append(stack[::]) # スタックの状態を保存
return result
利点
配列を走査しつつ、現在の要素よりも左側の要素すべてを調べたいとします。
Monotonic Stackの最後の要素だけが候補となる場合、計算量を改善することができます。
Brute Forceだと $O(N^2)$ かかるとことが、 $O(N)$に改善することができます。
上記コードは、二重ループがありつつも、どの要素もたかだか一度しかポップ/プッシュしないので、全体の計算量は$O(N)$です。(resultの生成以外)
典型問題 (Daily Temperatures)
Daily Temperatures より抜粋。
整数の配列 temperatures が与えられ、時系列順に、各日の気温を示すとします。
i番目の日は、その日より気温が高くなるまで、何日待つことになるか、各日にちに対して求めてください。
なお、そのような日が将来来ない場合には、0を答えとします。
例
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
これは、 temperatures を過去から未来に向かって走査し、monotonic stackを単調増加にすることで、効率的に計算することができます。
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
ans = [0] * n
stack = []
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
ans[j] = i - j
stack.append(i)
return ans
その他の簡単めの典型問題
https://leetcode.com/problems/remove-duplicate-letters/description/
https://leetcode.com/problems/online-stock-span/description/
https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/
Monotonic Stackの応用例
発展的な例を紹介します。典型問題を完全にマスターするまで無視奨励です。
Monotonic Deque
上記例では、配列をMonotonic Stackとして利用しました。
push/popができればいいわけなので、必ずしも配列である必要はなく、両端キュー(Deque, Double-ended queue)を使うこともできます。
利用先として、Sliding Window中の最大値を求めたいとき、Monotonic Dequeで効率的に求める例があります。
Dequeは単調増加に保ち、右から追加します。また、Windowの外にでた要素は左からポップします。
幅kのwindowの中の最大値を求めるコードを示します。
from collections import deque
def max_in_sliding_window(nums, k):
result = []
deq = deque()
for i in range(len(nums)):
# deqの左端がWindowの範囲外なら削除
while deq and deq[0] < i - k + 1:
deq.popleft()
# deqを単調増加に保つ
while deq and nums[deq[-1]] < nums[i]:
deq.pop()
deq.append(i)
if i >= k - 1:
result.append(nums[deq[0]])
return result
nums = [1,3,-1,-3,5,3,6,7]
k = 3
result = max_in_sliding_window(nums, k)
for i, curr_max in enumerate(result):
print(f"max in {i}:{i+k} is {curr_max}")
# max in 0:3 is 3
# max in 1:4 is 3
# max in 2:5 is 5
# max in 3:6 is 5
# max in 4:7 is 6
# max in 5:8 is 7
例題： Constrained Subsequence Sum
(なおこの問題は、Monotonic Dequeを用いずとも、PQ/平衡二分探索木を用いることで、充分効率的に解くことができます。)
Monotonic Deque + Binary Search
Monotonic Stackはソートされているので、Binary Searchが使えます。
ただし、Stackを単調減少にしたい場合、言語によっては標準ライブラリのBinary Searchは昇順でソートされていることが前提になっていて、そのままでは使えないでしょう。
ただ Stackに右からPush/Popするのではなく、Dequeに左からPush/Popすることで、単調増加にすることができます。
この場合、僅かな修正によって、標準ライブラリのBinary Searchが使えるようになるでしょう。
問題例：
どこかで見たんですが失念しました、ご存知のかた教えてくださいませ。
Push/Popのルールが複雑な例
Monotonic Stackへの追加・削除のルールが、単調性だけでなく、問題固有の条件が加わるパターンです。難しいです。