最小値を並べて持ち、いちばん小さい値をすぐ返すスタックを作る｜コーディング面接問題

問題

整数を積んでいくスタックを、クラス MinStack として作ってください。ふつうのスタックの操作に加えて、いま入っている値のうちいちばん小さい値を返す操作を持ちます。次の 4 つの操作を、どれも O(1) の時間でこなしてください。

push(x) は、整数 x をいちばん上に積みます。何も返しません
pop() は、いちばん上の値を取り除きます。何も返しません
top() は、いちばん上の値を返します。取り除きはしません
getMin() は、いま入っている値のうち、いちばん小さい値を返します

メソッドの名前は、JavaScript は上のまま、Python は get_min のように小文字と下線、Go は Push、Pop、Top、GetMin と頭を大文字にします。Go では newMinStack() で作ります。

入力は、呼ぶ操作の名前の並び ops と、それぞれの引数の並び args で渡します。ops の最初はクラスの名前で、args の最初は空の並びです。出力は操作ごとの戻り値の並びで、作った所と push、pop は null です。

pop、top、getMin は、スタックが空でないときだけ呼びます
x は -2147483648 以上 2147483647 以下です
操作の回数は 30000 回以下です

入力と出力の例

例 1

5、3、8 と積むと、いちばん小さいのは 3 です。8 を取り除いても 3 のまま、3 を取り除くと 5 に戻ります。

入力

ops = ["MinStack", "push",
  "push", "push", "getMin",
  "pop", "getMin", "pop",
  "getMin", "top"]
args = [[], [5], [3], [8],
  [], [], [], [], [], []]

出力

[null, null, null, null, 3,
 null, 3, null, 5, 5]

例 2

いちばん小さい値が 2 つ積まれていると、1 つ取り除いても、もう 1 つが残ります。

入力

ops = ["MinStack", "push",
  "push", "getMin", "pop",
  "getMin", "top"]
args = [[], [2], [2], [],
  [], [], []]

出力

[null, null, null, 2, null,
 2, 2]

例 3

負の数も入ります。

入力

ops = ["MinStack", "push",
  "push", "top", "getMin",
  "push", "pop", "pop",
  "getMin"]
args = [[], [-1], [-6], [],
  [], [0], [], [], []]

出力

[null, null, null, -6, -6,
 null, null, null, -1]

面接での聞かれ方

面接では、「元に戻す」の履歴や、関数の呼び出しの積み重ねを例に出して渡されることが多いです。

「いちばん小さい値を、毎回全部見ずに返してください」と、O(1) が条件に入ります
最小値を 1 つの置き場だけで持つ書き方を出すと、「その値を取り除いたら、次の最小値はどうやって知りますか？」と聞かれます
書き終えたあとに「記憶をもっと減らせますか？」「同じ値が何度も積まれたらどうなりますか？」と続きます

最小値は、取り除くたびに前の状態へ戻らなければなりません。「戻る先を、積むときに一緒に覚えておく」と気づけるかが芯です。

アルゴリズムのチートシートの「ハッシュマップ」に、この型の要点を表とコードでまとめています。

まず考える手順

段 1

まずは素直に、getMin が呼ばれるたびに、入っている値を全部見ていちばん小さい値を探す書き方を考えます。正しく動きますが、getMin が O(n) になり、条件を満たしません。

段 2

最小値を 1 つの置き場に持ち、積むたびに小さければ入れ替える書き方を考えます。積むほうは O(1) で済みますが、いちばん小さい値を取り除いたとき、次に小さい値が分かりません。また全部を見直すことになります。

段 3

スタックは上からしか取り除かないので、ある高さまで積んだときの最小値は、その上に何が積まれても変わりません。そこで、値の並び vals と並べて、「その高さまでの最小値」の並び mins を持ちます。積むときは、新しい値と mins のいちばん上の小さいほうを mins に積みます。

段 4

取り除くときは、vals と mins の両方から 1 つずつ取り除くだけです。mins のいちばん上は、自動的に 1 つ下の高さの最小値に戻ります。top は vals のいちばん上、getMin は mins のいちばん上を返せば、4 つとも O(1) です。

解答

Python

class MinStack:
    def __init__(self):
        self.vals = []
        self.mins = []

    def push(self, x):
        mins = self.mins
        m = x
        if mins:
            m = min(m, mins[-1])
        self.vals.append(x)
        mins.append(m)

    def pop(self):
        self.vals.pop()
        self.mins.pop()

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

    def get_min(self):
        return self.mins[-1]

JavaScript

class MinStack {
  constructor() {
    this.vals = [];
    this.mins = [];
  }

  push(x) {
    const mins = this.mins;
    const n = mins.length;
    let m = x;
    if (n > 0) {
      const last = mins[n - 1];
      m = Math.min(m, last);
    }
    this.vals.push(x);
    mins.push(m);
  }

  pop() {
    this.vals.pop();
    this.mins.pop();
  }

  top() {
    return this.vals.at(-1);
  }

  getMin() {
    return this.mins.at(-1);
  }
}

Go

type MinStack struct {
	vals []int
	mins []int
}

func newMinStack() *MinStack {
	return &MinStack{}
}

func (s *MinStack) Push(x int) {
	m := x
	if n := len(s.mins); n > 0 {
		m = min(m, s.mins[n-1])
	}
	s.vals = append(s.vals, x)
	s.mins = append(s.mins, m)
}

func (s *MinStack) Pop() {
	n := len(s.vals) - 1
	s.vals = s.vals[:n]
	s.mins = s.mins[:n]
}

func (s *MinStack) Top() int {
	return s.vals[len(s.vals)-1]
}

func (s *MinStack) GetMin(
) int {
	return s.mins[len(s.mins)-1]
}

vals と mins はいつも同じ長さです。Python の pop は値を返しますが、メソッドの最後で return していないので、操作の戻り値は None になります。Go の min は、1.21 から言語に備わった関数です。

計算量

時間は、4 つの操作のどれも O(1) です。並びの末尾に足すか、末尾を取り除くか、末尾を見るだけです
使う記憶は、積んでいる値の数を n として O(n) です。vals と mins で 2 倍持ちます
mins には「いまの最小値以下の値が積まれたときだけ」積み、取り除く値が mins の上と同じときだけ mins からも取り除くと、値がばらばらに積まれる場合の記憶を減らせます。そのときも時間は O(1) のままです

よくある間違い

最小値を 1 つの置き場だけで持つ。いちばん小さい値を取り除いた後、次に小さい値が分からなくなります。例 1 で 3 を取り除いた後、5 を返せません
記憶を減らす書き方で、「より小さい」ときだけ mins に積む。 同じ最小値が 2 回積まれたとき、mins には 1 回しか入りません。例 2 で 2 を 1 つ取り除くと mins が空になり、残っている 2 を返せません。「以下」のときに積みます
空のときに mins の上を読む。 最初の push で mins[-1] や mins[n - 1] を読むと、Python は並びの外の読み出しで止まり、JavaScript は undefined と比べて NaN を積みます。空かどうかを先に見ます

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

class MinStack: def __init__(self): # ここに持つ物を書きます pass def push(self, x): # ここに書きます pass def pop(self): # ここに書きます pass def top(self): # ここに書きます pass def get_min(self): # ここに書きます pass # 「実行」を押すと、下の行が動きます obj = MinStack() print(obj.push(5))

最小値を並べて持ち、いちばん小さい値をすぐ返すスタックを作る

問題