こんにちは、普段は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の実装例をあげます。

1.py

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への追加・削除のルールが、単調性だけでなく、問題固有の条件が加わるパターンです。難しいです。