Pythonで最小スタック（MinStack）を実装する方法 ― push・pop・top・getMinをすべてO(1)で

この記事では、push（要素の追加）、pop（要素の削除）、top（先頭要素の参照）、さらにgetMin（最小値の取得）をすべて定数時間 O(1) で実行できる特殊なスタック「最小スタック（Min Stack）」の実装方法を解説します。実装する関数は push(x)、pop()、top()、getMin() の4つです。

実装の考え方

通常のスタックでは最小値を求めるのに全要素を走査する必要がありますが、ここでは「現在の最小値（min）」を変数として保持し、pop時に正しく復元できるよう工夫することで、どの操作もO(1)で実現します。手順は以下の通りです。

• スタックを初期化するとき、min（最小値）を無限大（infinity）に設定します。
• push(x) の場合：
  • xが現在のmin以下であれば、まず古いminをスタックに退避してから、minをxに更新します。これにより、後から前の最小値を復元できます。
  • その後、xをスタックにプッシュします。
• pop() の場合：
  • 先頭要素をtとして取り出し、スタックから削除します。
  • tが現在のminと等しければ、その下に退避されていた旧最小値を新しいminとして復元し、その要素もスタックから取り除きます。
• top() の場合：
  • 単純にスタックの先頭要素を返すだけです。
• getMin() の場合：
  • 保持しているminをそのまま返します。

実装例

それでは、実際のPythonコードを見てみましょう。

class MinStack(object):
    def __init__(self):
        self.min = float('inf')
        self.stack = []

    def push(self, x):
        if x <= self.min:
            self.stack.append(self.min)
            self.min = x
        self.stack.append(x)

    def pop(self):
        t = self.stack[-1]
        self.stack.pop()
        if self.min == t:
            self.min = self.stack[-1]
            self.stack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min

m = MinStack()
m.push(-2)
m.push(0)
m.push(-3)
print(m.getMin())
m.pop()
print(m.top())
print(m.getMin())

動作確認

上記のコードを以下のように実行してみます。

入力

m = MinStack()
m.push(-2)
m.push(0)
m.push(-3)
print(m.getMin())
m.pop()
print(m.top())
print(m.getMin())

出力

-3
0
-2

処理の流れを追ってみる

出力結果が正しく得られる理由を簡単に確認しましょう。

• -2 をプッシュした時点で、minは -2 になります。
• 0 はminより大きいため、そのままスタックに積まれます。
• -3 をプッシュするとき、-3 ≤ -2 なので、旧minである -2 を退避してからminを -3 に更新します。したがって最初の getMin() は -3 を返します。
• pop() で -3 を取り除くと、tがminと一致するため、退避されていた -2 が新しいminとして復元されます。このとき top() は -2、再度の getMin() も -2 を返します。

この仕組みにより、すべての操作が追加のデータ構造なしに定数時間で完結する、効率的な最小スタックが実現できています。