問題と背景
MaxStack を実装します。push(x) は要素を追加し、pop() はスタックトップを削除して返し、top() はスタックトップを読み取り、peekMax() は最大値を読み取り、popMax() はスタックトップに最も近い最大値を削除して返します。重複する最大値は後入れ先出し（LIFO）のタイブレークルールを使用します。空スタックの動作は明示的なエラーまたは空の結果である必要があります。
公開されている LeetCode の問題や最近の面接質問の記録では、このインターフェースが使用されています。これはプレフィックス最小値スタックとは異なります。popMax は内部ノードを特定し、残りのスタック順序を復元する必要があります。
面接官が見ているポイント
- 重複する最大値のタイブレークと空スタックの規約を最初に確定させているか。
- 単一の
currentMax変数では削除後に次の最大値を復元できない理由を説明できるか。 - スタック順序と値の順序を分離し、両方のインデックスから同じノードを削除できるか。
- ならし計算量
O(1)の補助スタック設計と、O(log n)の順序付きインデックス設計を区別できているか。
コーディング前の確認事項
popMaxはO(1)である必要がありますか、ならしO(1)ですか、それともO(log n)でもよいですか？ これによりデータ構造が決まります。- 重複する最大値について、トップに最も近い要素を削除する必要がありますか、それとも任意の最大値で問題ありませんか？ ルールによってインデックスの検索方法が変わります。
- 安定したイテレータ、並行呼び出し、または永続性は必要ですか？ これらはノードのライフタイムとロックに影響します。
- 値は比較可能なオブジェクトですか、それとも範囲が制限された整数ですか？ 制限された整数ならバケットを使用できます。汎用オブジェクトは通常、比較インデックスが必要です。
30秒での回答
「各値を単調増加するシーケンス番号を持つノードにラップします。双方向連結リストでスタック順序を保持し、順序付きインデックスで (value, sequence) によってソートするため、その末尾エントリがトップに最も近い最大値になります。top はリストの末尾を読み取り、peekMax はインデックスの末尾を読み取り、popMax はそのノードを取得してリストのポインタを介して切り離します。平衡木インデックスを使用すると、push、pop、peekMax、popMax は O(log n) となり、top は O(1) です。トップ操作と peekMax のみが定数時間を必要とする場合は補助 max スタックの方が単純ですが、popMax を正確に O(1) に保つことはできません。」
ステップごとの詳細解説
ステップ 1: スタック順序とソート順序を分離する。
各ノードは value、単調増加する sequence、prev、および next を保持します。リストの末尾がスタックのトップになります。順序付けキーは (value, sequence) です。値が等しい場合、より大きなシーケンスが後方にソートされるため、インデックスの末尾がトップに最も近い最大値になります。
ステップ 2: 削除可能な順序付きインデックスを選択する。
重複に対応した平衡木、TreeMap と順序付きノードセットの組み合わせ、または値から順序付きシーケンス ID への2層インデックスを使用します。単一の currentMax では不十分です。それを削除した後、次の最大値とそのノードを見つける必要があるためです。
ステップ 3: 5つの操作すべてを同期させる。
push: ノードを作成し、リストの末尾に追加して、順序付きインデックスに挿入します。pop: リストの末尾を取得し、順序付きインデックスからそのノードを削除して、リストから切り離します。top: リスト末尾の値を返します。peekMax: 順序付きインデックスの末尾の値を返します。popMax: 順序付きインデックスの末尾を取得し、リストのポインタを介して切り離し、インデックスから削除します。
以下の擬似コードは重要な不変条件を示しています。具体的な木構造の API は言語によって異なります。
node = orderedByValueAndSequence.last()
orderedByValueAndSequence.erase(node.key)
unlink(node.prev, node, node.next)
return node.valueステップ 4: 計算量とよりシンプルな代替案。
平衡木を使用すると、top は O(1) であり、その他のインデックス操作は O(log n)、空間計算量は O(n) です。ならし O(n) の popMax が許容される場合、メインスタックに加えてプレフィックス max スタックを用意して各深さでの最大値を記録します。その方が実装は容易ですが、任意の位置での頻繁な削除には適していません。
ステップ 5: 重複、空状態、ノードの同一性。
シーケンス番号により、重複の順序付けと popMax のタイブレークの両方が解決されます。空の操作は一貫した1つのエラーを返します。各ノードはリストとインデックスにそれぞれ厳密に1回現れます。値のみから再構築するのではなく、両方の構造から同じノードを削除してください。
ステップ 6: 順序とインデックスのテスト。
遅い配列を参照モデルとして使用します。2回の popMax 呼び出しで [5,1,5] をテストします。トップの 5 を削除してから、ボトムの 5 を削除する必要があります。負の値、すべて同じ値、空状態、交互の push/pop、内部の最大値、繰り返しの削除、長いランダムなシーケンスをカバーします。すべての操作の後、リストの順序、インデックスのサイズ、および peekMax を検証します。
高品質な模範解答
「スタック順序には双方向連結リストを使用し、最大値の検索には (value, sequence) をキーとする平衡順序付きインデックスを使用します。シーケンス番号は増加するため、等しい最大値の中で最大のシーケンス番号を持つものがトップに最も近いものになります。各ノードはリストポインタとインデックスキーの両方を保持します。pop はリストの末尾を取得し、popMax はインデックスの末尾を取得し、両者とももう一方の構造から同じノードを削除します。top は O(1)、残りの操作は O(log n)、空間計算量は O(n) です。面接官が peekMax のみを必要とする場合は、実装の複雑さを軽減するために補助 max スタックを使用します。」
よくある間違い
- 現在の最大値を1つだけ保持する → 削除後に次の最大値が分からなくなる → 検索可能な順序付きインデックスを維持する。
- popMax を pop と同様に扱う → 誤った位置が削除され、スタック順序が変わってしまう → 値インデックスでノードを見つけ、リストポインタで切り離す。
- 重複にシーケンスを付けずに放置する → トップに最も近い最大値であることを証明できない →
(value, sequence)をキーにする。 - インデックスからは削除するがリストからは削除しない → top が削除されたノードを返す可能性がある → ノードの同一性を共有し、両方の構造をアトミックに更新する。
- 補助スタック設計で popMax が O(1) であると主張する → 任意の位置の削除は通常、要素の移動や状態の再構築を伴う → ならし計算量と最悪ケースの境界を正確に述べる。
フォローアップの質問と回答
フォローアップ 1: すべての操作を O(1) にできますか？
固定幅の整数の場合、バケット化または特殊な整数優先度構造が可能ですが、計算量の境界はキーの幅、メモリ、および計算モデルに依存します。任意の比較可能なオブジェクトの場合は、ならし、期待値、最悪ケースの主張を混同せず、率直に O(log n) のインデックスソリューションを提示してください。
フォローアップ 2: スレッドセーフにするにはどうしますか？
最もシンプルな規約は、リストと順序付きインデックスが一時的に乖離しないよう、各複合操作を1つのロックで保護することです。より高い並行性を実現するにはシャーディングや不変スナップショットを使用する場合がありますが、popMax は2つの構造からアトミックに削除するため、別々に取得したロックで十分であると仮定して一貫性を保つことはできません。
フォローアップ 3: popMax ではなく peekMax のみが必要な場合はどうなりますか？
メインスタックと同じ長さのプレフィックス max スタックを使用します。push は両方のスタックに新しい最大値を記録し、pop は両方から削除し、top と peekMax はそれぞれのトップを読み取ります。すべての操作は O(1) であり、重複する最大値は繰り返し記録される必要があります。