💬

【LeetCode】155. Min Stackを解く

2021/03/22に公開

アルゴリズムとデータ構造

tech

問題へのリンク

問題概要

push(x) -- スタックに要素xをpushする
pop() -- スタックの一番上から要素を取り除く
top() -- 一番上の要素を取得する
getMin() -- スタック内の最小要素を定数時間で返す

という機能を持つスタックを設計する．

例：

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

制約

$-2^{31} \leq val \leq -2^{31} - 1$
pop, getMinメソッドは必ず，空でないスタックに対して呼び出される
最大で $3 \times 10^4$ 回の呼び出しがある

考えたこと

基本的なスタックの処理であるpush，pop，topについては素直に実装すれば問題なさそう．

ただし，getMinに関しては定数時間という制約がある．
つまり，このメソッドが呼び出された際にスタック全体を探索するような実装では $O(n)$ の計算量となるため条件を満たさないので何らかの工夫をする必要がある．

では，どのように実装したらよいのだろうか？

スタックは後入れ先出し（LIFO: Last In First Out）の構造でデータを保持している．
したがって，pushする際は現在の最小値mと追加される値xを比較して小さい方を保持すればよいことが分かる．
また，popすることを考えると(x, m)というデータを保持することで定数時間でgetMinの処理を行うことができるとわかる．

以上の考えに基づいた実装は以下のとおりである：

class MinStack(object):

    def __init__(self):
        self.data = []

    def push(self, x):
        if len(self.data) == 0:
            minVal = x
        else:
            minVal = min(self.getMin(), x)
        self.data = [(x, minVal)] + self.data

    def pop(self):
        self.data = self.data[1:]

    def top(self):
        return self.data[0][0]

    def getMin(self):
        return self.data[0][1]

問題概要

制約

考えたこと

Discussion