NeetCodeのSolutionを書いていく

#

Minimum Stack

#

問題概要

#

push,pop,top,getMinをサポートするstackクラスを作りましょう。 MinStack()でスタックを初期化します。 pushでスタックに要素を積みます。 popでスタックの一番上の要素を取り出します。 topでスタックの一番上の要素を読みます。 getMinでスタックに含まれる最小値を取得します。

全ての関数はO(1)で動きます。

例

#

Input: [“MinStack”, “push”, 1, “push”, 2, “push”, 0, “getMin”, “pop”, “top”, “getMin”] Output: [null,null,null,null,0,null,2,1]

Explanation:
MinStack minStack = new MinStack();
minStack.push(1);
minStack.push(2);
minStack.push(0);
minStack.getMin(); // return 0
minStack.pop();
minStack.top();    // return 2
minStack.getMin(); // return 1

制約

#

valは-2^31 以上、2^31-1以下。4byte符号付き整数な感じ。 pop,top,getMinは常に空ではないスタックに対して呼び出される。

計算時間:O(1) メモリ:O(n)

メモ

#

今までに無い珍しい問題形式。 クラス関数の複数実装を求められる。 スタックの持ち方も含めて問われている感じ？ というか、listのpush popをそのまま使っていいのか？

どうやら min(self.stack) がO(n)になるらしい。 getMinをどうやってO(1)にするかという問題ですね。

push、popのタイミングで最小値を更新して保持しておけば良い？ しかしこれだと、popのタイミングで現在の最小値がスタックに存在しなくなるケースで、その次に小さい値を取得するよう方法が必要になっちゃう。 ではその「次に小さい値」を取得するのはどうやんねん、という最小値を保持するためにはリストから最小値を探さないといけないという堂々巡りの問題になってしまう。

popの時に以下に最小値を取得するかが問題なので、popの時に最小値を保持するためのmin_val_stackを別途用意しておけばよいか。

class MinStack:
    stack: list[int]
    min_val_stack: list[int]
    min_val: int

    def __init__(self):
        self.stack = []
        self.min_val_stack = []
        self.min_val = 2**31 - 1

    def push(self, val: int) -> None:
        if self.min_val > val:
            self.min_val = val
        self.stack.append(val)
        self.min_val_stack.append(self.min_val)

    def pop(self) -> None:
        self.stack.pop(-1)
        self.min_val_stack.pop(-1)
        if len(self.min_val_stack) > 0:
            self.min_val = self.min_val_stack[-1]
        else:
            self.min_val = 2**31 - 1

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

    def getMin(self) -> int:
        return self.min_val