最小スタック

ホーム
/問題
/スタックの技
/最小スタック

Medium (中)カテゴリ: stack

問題

スタックの基本操作（push、pop、top）をサポートし、さらに最小要素を定数時間で取得する操作（getMin）をサポートする「MinStack」クラスを設計してください。実装すべきメソッド： - `MinStack()` - スタックオブジェクトを初期化します。 - `void push(int val)` - 要素 val をスタックにプッシュします。 - `void pop()` - スタックの先頭要素を削除します。 - `int top()` - スタックの先頭要素を取得します。 - `int getMin()` - スタック内の最小要素を取得します。

例

例 2:

入力:

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

出力:

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

説明:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // -3を返す minStack.pop(); minStack.top(); // 0を返す minStack.getMin(); // -2を返す

制約

-2^31 <= val <= 2^31 - 1
pop、top、getMinの各操作は、スタックが空でない場合にのみ呼び出されます
push、pop、top、getMinの各操作の呼び出しは合計で最大3 * 10^4回です

解法

アプローチ

この問題を解くための効率的なアプローチは、2つのスタックを使用することです。1つは通常の要素を格納するためのスタック、もう1つは現在の最小値を追跡するためのスタックです。【解法の流れ】 1. 2つのスタックを初期化します： - `stack`: 通常の要素を格納するスタック - `minStack`: 各時点での最小値を格納するスタック 2. `push(val)` 操作： - `val` を `stack` にプッシュします - `minStack` が空の場合、または `val` が現在の最小値以下の場合、`val` を `minStack` にもプッシュします 3. `pop()` 操作： - `stack` から要素をポップします - ポップされた要素が現在の最小値と等しい場合、`minStack` からも要素をポップします 4. `top()` 操作： - `stack` の先頭要素を返します 5. `getMin()` 操作： - `minStack` の先頭要素を返します【視覚的な例】例えば、次の操作シーケンスを考えてみましょう： ``` MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // -3を返す minStack.pop(); minStack.top(); // 0を返す minStack.getMin(); // -2を返す ``` 各操作後のスタックの状態： 1. 初期状態： - stack: [] - minStack: [] 2. push(-2)： - stack: [-2] - minStack: [-2] // -2は最初の要素なので、最小値 3. push(0)： - stack: [-2, 0] - minStack: [-2] // 0は-2より大きいので、minStackには追加されない 4. push(-3)： - stack: [-2, 0, -3] - minStack: [-2, -3] // -3は現在の最小値-2より小さいので、minStackに追加 5. getMin()： - minStack.top() = -3を返す 6. pop()： - stack: [-2, 0] // -3を削除 - minStack: [-2] // -3は最小値だったので、minStackからも削除 7. top()： - stack.top() = 0を返す 8. getMin()： - minStack.top() = -2を返す【代替アプローチ】 1. 各要素と現在の最小値のペアを1つのスタックに格納する方法 2. 各要素をノードとして格納し、各ノードに現在の最小値も保持させる方法どちらのアプローチも、すべての操作を定数時間で実行できます。

計算量

時間計算量

すべての操作（push、pop、top、getMin）: O(1)

空間計算量

O(n) - n はスタックに格納される要素の数

実装

java

python

javaの実装

/**
 * 最小スタック（Min Stack）問題の解法
 * 
 * 【問題】
 * スタックの基本操作（push、pop、top）をサポートし、さらに最小要素を定数時間で取得する操作（getMin）を
 * サポートする「MinStack」クラスを設計する。
 * 
 * 【アプローチ】
 * 2つのスタックを使用：
 * 1. 通常のスタック：すべての要素を格納
 * 2. 最小値スタック：各時点での最小値を追跡
 * 
 * 【計算量】
 * - 時間計算量: すべての操作 O(1)
 * - 空間計算量: O(n) - n はスタックに格納される要素の数
 */
class MinStack {
    private Stack<Integer> stack;      // 通常の要素を格納するスタック
    private Stack<Integer> minStack;   // 最小値を追跡するスタック
    
    /** スタックを初期化 */
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    /** 要素をスタックにプッシュ */
    public void push(int val) {
        // 通常のスタックに要素をプッシュ
        stack.push(val);
        
        // 最小値スタックが空か、新しい値が現在の最小値以下の場合
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    /** スタックの先頭要素を削除 */
    public void pop() {
        // 削除する要素が現在の最小値と等しい場合、最小値スタックからも削除
        if (stack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        
        // 通常のスタックから要素を削除
        stack.pop();
    }
    
    /** スタックの先頭要素を取得 */
    public int top() {
        return stack.peek();
    }
    
    /** スタック内の最小要素を取得 */
    public int getMin() {
        return minStack.peek();
    }
}

Java

解説

このJavaの実装では、2つのスタックを使用して最小スタックを効率的に実装しています。

【詳細な解説】

1. **データ構造**: - `stack`: 通常の要素を格納するスタック - `minStack`: 各時点での最小値を追跡するスタック

2. **push(val) 操作**: - 新しい要素 `val` を通常のスタック `stack` にプッシュします。 - `minStack` が空の場合、または `val` が現在の最小値以下の場合、`val` を `minStack` にもプッシュします。 - これにより、`minStack` の先頭には常に現在のスタック内の最小値が格納されます。

3. **pop() 操作**: - 削除する要素が現在の最小値と等しい場合、`minStack` からも要素を削除します。 - これにより、`minStack` の先頭には常に残りの要素の中での最小値が格納されます。 - 注意点として、`equals()` メソッドを使用して比較しています。これは、Javaでは `Integer` オブジェクトの比較に `==` を使用すると、値ではなく参照が比較される可能性があるためです。

4. **top() 操作**: - 通常のスタック `stack` の先頭要素を返します。

5. **getMin() 操作**: - 最小値スタック `minStack` の先頭要素を返します。 - これにより、現在のスタック内の最小値を定数時間で取得できます。

【具体例】

``` MinStack minStack = new MinStack(); minStack.push(-2); stack: [-2], minStack: [-2] minStack.push(0); stack: [-2, 0], minStack: [-2] minStack.push(-3); stack: [-2, 0, -3], minStack: [-2, -3] minStack.getMin(); // -3を返す minStack.pop(); stack: [-2, 0], minStack: [-2] minStack.top(); // 0を返す minStack.getMin(); // -2を返す ```

この実装の優れている点は、すべての操作が定数時間 O(1) で実行できることです。また、最小値を追跡するために必要な追加のスペースは、最悪の場合でも O(n) です（すべての要素が降順に挿入される場合）。

追加のメモ

最小スタック問題は、データ構造の設計と効率的な操作の実装を学ぶための良い例です。この問題には複数の解法があり、それぞれに利点と欠点があります。【異なる解法の比較】 1. **2つのスタックを使用するアプローチ** - 時間複雑度: すべての操作 O(1) - 空間複雑度: O(n)（最悪の場合）、平均的には O(log n) 程度 - 利点: メモリ効率が良い（最小値が変わらない場合） - 欠点: 2つのデータ構造を管理する必要がある 2. **値と最小値のペアを格納するアプローチ** - 時間複雑度: すべての操作 O(1) - 空間複雑度: O(n) - 利点: 実装がシンプル、1つのデータ構造のみ - 欠点: 各要素に最小値も格納するため、メモリ使用量が増える 3. **ノードベースのアプローチ** - 各ノードに値と現在の最小値を格納 - 時間複雑度: すべての操作 O(1) - 空間複雑度: O(n) - 利点: カスタムデータ構造を使用できる - 欠点: 実装が少し複雑になる【実装上の注意点】 1. **Javaでの実装** - `Integer` オブジェクトの比較には `equals()` メソッドを使用する - `==` 演算子は参照の比較になるため、値の比較には適さない 2. **Pythonでの実装** - リストを使用してスタックを実装する場合、`append()` と `pop()` メソッドを使用する - タプルを使用して値と最小値のペアを格納する 3. **エッジケース** - スタックが空の場合の処理 - 同じ値が複数回プッシュされる場合の処理【関連する問題】 - 「最大スタック」（Max Stack）: 最大要素を定数時間で取得する操作をサポートするスタック - 「スタックを使用したキュー」（Implement Queue using Stacks）: スタックを使用してキューを実装 - 「O(1)時間の増分操作を持つスタック」（Design a Stack With Increment Operation）: 特定の範囲の要素を増分する操作をサポートするスタックこの問題は、データ構造の設計と効率的な操作の実装を学ぶための基本的な問題です。実際のアプリケーションでも、特定の条件下で最小値や最大値を効率的に取得する必要がある場合があります。

問題一覧に戻る