大企業の面接官によく聞かれるアルゴリズム図：スタック内の最小値を見つける方法がまだわかりませんか？

今日のインタビューの質問はこれです...

トピック

スタックデータ構造を定義します。この型でスタックの最小要素を取得できる min 関数を実装してください。このスタックでは、min、push、pop を呼び出す時間の計算量は O(1) です。

例：

 MinStack を新しい MinStack() に追加します。  
 minStack.push(-2);  
 minStack.push(0);  
 minStack.push(-3);  
 minStack.min (); --> -3 を返します。    
 minStack.pop();  
 minStack.top (); --> 0 を返します。    
 minStack.min (); --> -2 を返します。    
 LeetCode アドレス: leetcode-cn.com/problems/ba…

考える

まず、この質問自体は理解しやすいのですが、その実装の難しさは次の 2 つの点にあります。

• ポップ（スタックの一番上の要素を削除する）操作を実行するときに、現在の最小値を削除した場合、次の最小値をどのように見つけるのでしょうか。
• min、push、popの呼び出しの時間計算量がO(1)であることを確認します。

つまり、pop を実行するときにスタック内の最小の値を削除する場合、スタック内の次の最小の要素をどのように見つけるのでしょうか。また、操作の時間計算量が O(1) であることを確認する必要があります。この時間計算量により、最小値を削除した後に次の最小値を見つけるための走査が制限されるため、これがこの問題の難しさになります。

たとえば、次の最上位要素の値を削除するとします。

最小値は 1 なので、次の図に示すように、削除後に最小値も削除されます。

それでは、3分間考えて、この問題にどう対処するか考えてみましょう〜

問題解決

実際、スタックにプッシュするたびに、現在の要素が最小値より小さいかどうかを判断できます。小さい場合は、元の最小値と最新の最小値を次々にスタックにプッシュできます。このように、pop の呼び出し時に最小値が削除されても、次の要素を取得することで新しい最小値を取得できます。実行プロセスは次のとおりです。

ステップ1

最初の要素をスタックにプッシュします。最初の要素なので、最小値はこの要素の値になります。

ステップ2

以下に示すように、2 番目の要素をスタックにプッシュします。

スタックにプッシュされた要素 3 は 8 より小さいため、スタック内の元の最小値 8 が最初にスタックに格納され、次に 3 がスタックにプッシュされます。

ステップ3

以下に示すように、3 番目の要素をスタックにプッシュします。

スタックにプッシュされた要素 5 は 3 より大きいため、スタック内の最小値は変更されず、要素 5 が直接スタックにプッシュされます。

ステップ4

以下に示すように、スタックをプッシュし続けます。

スタックにプッシュされた要素 1 は 3 未満なので、元の最小値 3 が最初にスタックにプッシュされ、次に 1 がスタックにプッシュされ、スタック内の最小値が 1 に変更されます。

ステップ5

次の図に示すように、ポップ操作を実行します。[画像のアップロード中...(image-f68dcf-1602769401330-6)]

要素 1 がスタックからポップされ、現在の要素がスタックの最小値であると判断されるため、次の図に示すように、最上位の要素 3 が最小値に設定され、要素 3 が削除されます。

ステップ6

以下に示すように、スタックのポップを続けます。

要素 5 は現在の最小値ではないため、スタックから直接ポップされます。

ステップ7

以下に示すように、スタックのポップを続けます。

ポップされた要素 3 は最小値なので、次の図に示すように、引き続き最小値を最上位要素 8 に設定し、最上位要素をポップします。

この方法では、残る要素は 1 つだけです。最後の要素がスタックからポップされると、スタックは空になり、プロセス全体が完了します。

実装コード1

次に、上記のアイデアをコードで実装します。配列によって実装されたスタックを使用して、関連する機能を実装します。コードは次のとおりです。

クラス MinStack {
    private int [] data; // スタックデータ
    private int maxSize; // 最大長
    プライベートint   top ; // スタックの先頭ポインタ（添え字）
    プライベートint   min ; // 最小値
 
    // コンストラクタ
パブリックMinStack() {
        // デフォルト値を設定する
        最大サイズ = 10000;
        データ = 新しいint [maxSize];
上= -1;
最小値= Integer.MAX_VALUE ;
    } 
 
    // スタックにプッシュする（要素を追加する）
パブリックボイドプッシュ( int x) {
        （最小値＞＝x）の場合
            // より小さい値に遭遇したら、元の最小値を記録する（スタックにプッシュする）
            データ[++上部] = min ;
最小値= x;
        }
        //現在の値をスタックにプッシュします
        データ[++上部] = x;
    } 
 
    // スタックをポップする（一番上の要素を削除する）
パブリックvoidポップ（）{
        if ( min == data[ top ]) {
 min = data[ --top]; // 元の最小値を取得し、スタックからポップします 
        }
 --top; // スタックをポップする 
    } 
 
    // スタックの一番上の要素を見つける
公共 整数 トップ() {
データを返す[先頭];
    } 
 
    // 最小値を照会する
公共 整数 最小（）{
戻る 分;
    }
 }

LeetCode での上記コードの実行結果は次のとおりです。

パフォーマンスは依然として非常に高く、ユーザーの 99.92% を超えており、メモリ消費量も大きくないことがわかります。そのコアコードは push メソッドにあり、最初に元の最小値と最新の最小値をスタックに次々にプッシュします。スタックをポップするときに、ポップされた要素が最小値かどうかを判断します。最小値の場合、現在の最小値はスタックの先頭要素を指し、スタックの先頭要素がポップされ、次の新しい最小値が得られます。

実装コード2

カスタム配列スタックを使用したくない場合は、Java の組み込みスタックを使用してこの関数を実装することもできます。コードは次のとおりです。

クラス MinStack {
    プライベート Stack< Integer > stack = new Stack<>();
    プライベートint  最小値= Integer.MAX_VALUE ; 
 
パブリックMinStack() { } 
 
    // スタックにプッシュする（要素を追加する）
パブリックボイドプッシュ( int x) {
        (x <=最小)の場合{
            // より小さい値に遭遇したら、元の最小値を記録する（スタックにプッシュする）
            スタックをプッシュします(最小値);
最小値= x;
        }
        スタックをプッシュします。
    } 
 
    // スタックをポップする（一番上の要素を削除する）
パブリックvoidポップ（）{
        （stack.pop() == min ）の場合{
 min = stack.pop(); // 元の最小値を取得する
        }
    } 
 
    // スタックの一番上の要素を見つける
公共 整数 トップ() {
 stack.peek()を返します。
    } 
 
    // 最小値を照会する
公共 整数 最小（）{
戻る 分;
    }
 }

LeetCode での上記コードの実行結果は次のとおりです。

結果から、Java の組み込みスタックを使用した場合のパフォーマンスはカスタム配列のスタックほど良くないことがわかりますが、それでもコードはテストに合格しました。この実装の利点は、コードが比較的単純であり、Java 独自の API を使用して最小値の検索を完了できることです。

このコードの実装方法 (Java API を使用) は、特に指定がない限り、質問の練習や実際の面接で直接使用できます。

要約する

この記事では、カスタム配列スタックと Java API の Stack という 2 つの方法を使用して、スタック内の最小値関数を実装し、スタックの min、push、pop メソッドを呼び出すときの時間計算量が O(1) になるようにします。 2 つの実装方法のコードは若干異なりますが、実装の考え方は同じです。要素をスタックにプッシュするときに、現在の要素が最小要素より小さいかどうかを判断します。最小要素より小さい場合は、最初に元の最小値がスタックにプッシュされ、次に現在の最小要素がスタックにプッシュされます。このように、pop メソッドが呼び出されると、最小値が削除されても、次の要素を取り出して新しい最小値にするだけで済みます。このようにして、min、push、および pop メソッドの呼び出しの時間計算量は O(1) として達成できます。