Min Stack
通常のpush、pop、topに加えて、保持している最小値をgetMinで返せるスタックを設計してください。4つの操作はそれぞれO(1)時間で実行できなければなりません。
操作は順番にopsとして与えられます。args[i]には、pushの場合は値が、それ以外のすべての操作では0が格納されています。空の状態から始まる1つのスタックに対して操作を実行し、各操作につき1つの文字列を返してください。pushとpopでは"null"を、topとgetMinでは数値をテキストとして返します。
関数
- opsstring-array
- 実行される順序での操作
- argsinteger-array
- 各 push の値、それ以外のすべての操作では 0
- 戻り値string-array
- 操作ごとに1つの回答をテキストとして
制約
1 ≤ ops.length ≤ 3000args.length == ops.length- 各
ops[i]はpush、pop、topまたはgetMinです。 -231+1 ≤ args[i] ≤ 231-1の場合は push、その他の操作の場合はargs[i] == 0。pop、top、getMinは、スタックに少なくとも1つの値が格納されている場合にのみ呼び出されます。
例
- 入力
- ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
- 出力
- ["null", "null", "null", "1", "null", "1", "null", "4"]
- 説明
- スタックには下から順に 4、1、7 が格納されているので、最小値は 1 です。7 をポップすると、1 が一番上に残ります。さらに 1 をポップすると 4 だけが残るため、最小値は 4 に戻ります。
- 入力
- ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
- 出力
- ["null", "null", "null", "-2", "null", "-2", "null", "3"]
- 説明
- 最小値の -2 は2回プッシュされます。最初のポップで1つが取り除かれ、もう1つはまだ残っているため、
getMinは -2 のままです。2回目のポップの後にのみ、最小値は3に戻ります。
- 入力
- ops = ["push", "push", "pop", "push", "getMin", "top"]args = [2, 0, 0, 8, 0, 0]
- 出力
- ["null", "null", "null", "null", "2", "8"]
- 説明
- 0 はプッシュされてから再びポップされるため、もう数に含まれません。その後、スタックには 2 と 8 が残ります。トップは 8 で、最小値は 2 です。
提出時に隠しテスト+16件
発展問題
償却 O(1) 時間で最小値も報告する、先入れ先出しキューを実装できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最小値を保持する変数が1つあれば、その最小値をポップするまでは機能します。その時点で何を知っておく必要がありますか。また、それをいつ書き留めておくことができたでしょうか。
スタックは最上部でのみ変化するため、ある高さより下にある値の最小値は、その高さまで要素が積まれている限り変わりません。プッシュするときに最小値を記録しましょう。
値の横に2つ目のスタックを用意します。新しい値がそのスタックのトップ以下ならそこにプッシュし、メインスタックから取り出す値がそのトップと等しければポップします。すると、そのトップが常に
getMinの答えになります。
解説
通常のスタックでは、push、pop、topはすでにO(1)で実行できます。難しいのは、popの後も維持される最小値です。重要なのは、スタックは一番上でしか変化しないということです。ある高さに値がある間、その下にあるものは変化しないため、その高さまでのすべての値の最小値は固定されています。pushするときにその最小値を記録しておけば、popすると前の最小値が自動的に復元されます。各手法の違いは、何を記録するかです。
getMin のたびにスタックを走査する
考え方
push、pop、topには通常のスタックを使い、getMinでは保持しているすべての値を調べて最小値を求めます。呼び出された時点で実際の内容を確認するため、これは常に正しい方法です。
ただし、O(1)という要件を満たせません。n個の値があるスタックでgetMinを呼び出すと、そのn個すべてを読み取ります。1,500個の値をプッシュし、プッシュのたびにgetMinを呼び出す隠しテストでは、約1,500 × 1,500 / 2、つまり100万個を超える値を読み取ります。一方、ほかの方法では呼び出しごとに1個を読み取ります。このような操作を10^5回実行するシステムでは、数十億個もの値を読み取ることになります。
最小値を1つキャッシュしても解決しません。最小値を保持する変数はプッシュには有効ですが、その値をポップすると、もう一度すべて調べない限り、次に小さい値が何か分かりません。
アルゴリズム
- 値をスタックとして使うリストに格納します。
push xの場合はxを追加し、popの場合は最後の値を削除し、topの場合はその値を読み取ります。getMinの場合は、格納されているすべての値を調べ、最小値を返します。- 各答えをテキストとして記録し、リストを返します。
class MinStack:
def __init__(self):
self.values = []
def push(self, x):
self.values.append(x)
def pop(self):
self.values.pop()
def top(self):
return self.values[-1]
def getMin(self):
# Look at every stored value: O(n).
smallest = self.values[0]
for v in self.values:
if v < smallest:
smallest = v
return smallest
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return result各値の横に最小値を保存する
考え方
値がスタックの高さ i にある間、その下にある値は変化しないため、下から i 個の値の最小値は、その値がそこにある限り固定されます。その数値を各値の隣に保存します。minsという2つ目のスタックを用意し、mins[i]をvalues[0..i]の最小値とします。
プッシュ時には、minsに追加する新しい要素に、xとその1つ下の要素のうち小さい方を保存します。ポップ時には、両方のスタックのトップを取り除きます。すると、minsのトップは残った値の最小値になります。getMinはminsのトップを読み取ります。
最初の例では、4、1、7をプッシュすると、最小値として4、1、1が保存されます。7をポップするとminsのトップには1が残り、1をポップすると4が残ります。各操作で触れるのは2つのスタックのトップだけなので、どの操作もO(1)です。その代わり、値ごとに数値をもう1つ保存します。
アルゴリズム
- 高さが等しい2つのスタック、
valuesとminsを用意します。 push xの場合、xをvaluesにプッシュし、xとminsのトップのうち小さい方をminsにプッシュします（minsが空ならx自体をプッシュします）。popの場合、両方のスタックからポップします。topの場合はvaluesのトップを読み取り、getMinの場合はminsのトップを読み取ります。- 各答えをテキストとして記録し、リストを返します。
class MinStack:
def __init__(self):
self.values = []
self.mins = [] # mins[i] is the smallest of values[0..i]
def push(self, x):
self.values.append(x)
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.values.pop()
self.mins.pop()
def top(self):
return self.values[-1]
def getMin(self):
return self.mins[-1]
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return result新しい最小値が現れたときだけ増える最小値のスタック
考え方
2つ目の方法では、minsはしばしば同じ値を繰り返します。1をプッシュし、続けて7、8、9をプッシュすると、minsには1、1、1、1が格納されます。同じ値が繰り返されても、新しい情報は得られません。そこで、値が最小値になったときだけminsに記録し、その値がvaluesから取り除かれるときに削除します。
プッシュ時には、minsが空であるか、xがその先頭の値以下なら、xをminsに追加します。ポップ時には、valuesから取り除かれる値がminsの先頭の値と等しければ、minsからもポップします。minsの先頭の値は常に現在の最小値です。その値より後にプッシュされた値は、より大きいか、それ以下で同じく記録され、その後すでにポップされているためです。
比較には<=を使う必要があり、<ではいけません。2つ目の例では、-2が2回プッシュされます。<の場合、最初の1つだけが記録され、最初のポップでそれがminsから取り除かれるため、スタックに-2がまだ残っているのに、getMinは3を返します。<=なら、それぞれの値が個別に記録されます。
4つの操作はすべてO(1)のままです。値が大きいものから小さいものへと追加される場合、minsはvaluesと同じ高さまで増えます。最小値がめったに変わらない場合は、短いままです。
アルゴリズム
- スタック
valuesとスタックminsを用意します。 push xの場合、xをvaluesにプッシュします。minsが空であるか、xがそのトップ以下であれば、xもminsにプッシュします。popの場合、valuesからポップします。取り除いた値がminsのトップと等しければ、minsからもポップします。topの場合、valuesのトップを読み取ります。getMinの場合、minsのトップを読み取ります。- 各回答をテキストとして記録し、リストを返します。
class MinStack:
def __init__(self):
self.values = []
self.mins = [] # each value that was a minimum when pushed; the top is the current minimum
def push(self, x):
self.values.append(x)
# <= keeps one copy per equal minimum, so popping one leaves the others.
if not self.mins or x <= self.mins[-1]:
self.mins.append(x)
def pop(self):
if self.values.pop() == self.mins[-1]:
self.mins.pop()
def top(self):
return self.values[-1]
def getMin(self):
return self.mins[-1]
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return result
落とし穴と境界ケース
ここでのバグは、最小値の重複と、pop で何が取り除かれるかに関するものです。
xが厳密に小さい場合にのみ新しい最小値を記録すること。すると、最小値の2つ目のコピーがminsに記録されず、1つ目のコピーをポップすると、2つ目がまだスタックに残っているのに最小値が失われます。2つ目の例でこれが分かります。- 最小値を1つの変数に保持すること。プッシュには対応できますが、最小値がポップされた後は変数が古い値のままになり、次に小さい値を見つけるには走査が必要です。
- ボックス化された整数を参照で比較すること。Java では、
Integer == Integerは両方が同じオブジェクトかどうかを調べます。Java がキャッシュする -128 から 127 までの値ではたまたま成り立ちますが、それより大きい値のほとんどでは成り立たないため、ポップ時のチェックは大きな値でのみ失敗します。Java のコードのように、先にintにアンボックスしてください。 - 3つ目の方法で、ポップするたびに
minsをポップすること。取り除かれた値がそのトップにある場合にのみサイズを減らします。2つ目の方法では、2つのスタックは常に一緒に動きます。 popに数値を返させること。この形式では、pushと同様にpopは"null"を返します。
よくある質問4
スタックの最小値をO(1)時間で取得するにはどうすればよいですか？
プッシュ時に最小値を記録します。スタックが変化するのはトップだけなので、ある高さが埋まっている間、その高さより下の値の最小値は変化しません。各高さでの最小値、または新たな最小値だけを保持する2つ目のスタックを用意すれば、getMinはそのトップを読み取るだけになります。
値が現在の最小値と等しいとき、なぜ最小値スタックにプッシュするのですか？
最小値がスタックに複数回存在することがあるためです。厳密に小さい値だけを記録すると、-2 が2つあっても mins のエントリは1つだけになります。最初に -2 をポップするとそのエントリが削除され、2つ目の -2 がまだ存在するにもかかわらず、getMin は以前の最小値を返します。同じ値も記録すれば、それぞれの値に専用のエントリが用意されます。
Min Stack は追加の空間計算量 O(1) で実装できますか？
はい、1つのスタックと1つの変数 min を使います。現在の最小値より小さい x をプッシュするときは、代わりに 2x - min を格納し、min = x に設定します。格納された数値はその時点で min より小さくなり、これが目印になります。目印の付いた数値をポップすると、以前の最小値は 2 * min - stored です。この計算は限界値付近で32ビット整数の範囲を超えるため、64ビット値が必要です。また、符号のロジックは間違えやすいため、面接官の多くは2つのスタックを使う方法で問題ありません。
Min Stack の時間計算量と空間計算量は何ですか？
すべての操作は O(1) です。push、pop、top、getMin はそれぞれ、1つまたは2つのスタックの先頭だけを読み取るか変更します。n 個の値を格納する場合、空間計算量は O(n) です。各値の隣に最小値を格納すると、常に 2n 個のスロットを使用します。新しい最小値だけを格納すると、n + 1 個から 2n 個の間になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def minStackOps(ops, args):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"] args = [4, 1, 7, 0, 0, 0, 0, 0]
期待値
["null", "null", "null", "1", "null", "1", "null", "4"]