問題と適用シナリオ
heights が与えられたとき、各値は幅 1 のヒストグラムのバーを表します。有効な長方形は1つ以上の 連続するバーにまたがり、ベースラインから始まり、その区間内の 最も低いバーよりも高くなることはできません。その最大面積を返してください。
heights = [2, 1, 5, 6, 2, 3]
answer = 10最適な長方形はインデックス 2..3 をカバーします。その高さは 5、幅は 2、面積は 10 です。 標準的な制約は 1 <= heights.length <= 100000 および 0 <= heights[i] <= 10000 です。本記事 では、空の入力に対して 0 を返すようにも定義しています。標準的な制約の下では、面積は最大で 10^9 であり、これは JavaScript の number 型で正確に表現可能です。
現在の英語の面接準備資料および独立した中国語の公開ソリューションの双方が、 このまったく同じ問題を単調スタックの演習として提示しています。元の問題と最新の DSA ガイドは同じ幅 1 のモデルと制約を使用しています。このことは、特定の企業に帰属させたり検証不能な頻度を主張したりすることなく、これを代表的な coding の問題として扱う根拠となります。
面接官が評価している点
第1のシグナルは、すべての境界のペアを列挙することなく、考えられるすべての長方形をモデル化できるかどうかです。任意に選んだ高さに対して、最適な長方形は左右それぞれの側で最初の 厳密に低いバーの手前まで広がります。これにより、幾何学的に見える問題が「最も近いより小さい境界」のクエリへと変換されます。
第2のシグナルは、データ構造を導出できるかどうかです。高さが増加するスタックは、 右側の境界がまだ不明なバーを保持します。より低いバーが出現すると、それらの 長方形の1つ以上が確定（クローズ）します。現在のインデックスはそれらの右側にある最初のより低い位置であり、各バーとともに保存された開始位置は、 それがどこまで左に拡張できるかをすでにエンコードしています。
第3のシグナルは、重複や境界における正当性です。同じ高さによって、 異なる開始位置を持つ競合エントリが作成されるべきではありません。最後にスタックに残ったバーにも、依然として右側の 境界が必要です。優れた実装では、暗記した幅の公式に頼るのではなく、 両方のルールを明示的にします。
最後に、ネストされた while ループにはならし解析が必要です。1回の反復で多数のエントリをポップすることがありますが、 各エントリは1回プッシュされ、1回ポップされます。スタック操作の総数は線形です。
回答前の確認事項
- すべてのバーの幅は
1ですか？ はい。幅が可変の場合、保持する左側の境界と面積の計算式の両方が変わります。 - 長方形は連続したバーを使用する必要がありますか？ はい。長方形が途中の低いバーをスキップすることはできません。
- 高さに 0 や重複が含まれることはありますか？ はい。0 は正の長方形を分割します。等しい高さには一貫したスタックルールが必要です。
- 入力が空になることはありますか？ 標準的な問題では除外されていますが、この実装では文書化された拡張として
0を返します。 - 面積のみを返せばよいですか？ はい。座標を返すには、最適解の開始位置、終了位置、高さ、およびタイブレーク（同点時の優先）ルールを保持する必要があります。
- 関数が入力を変更（破壊）してもよいですか？ 変更は不要です。番兵は配列の末尾に追加するのではなく、仮想的に扱われます。
- 面積がオーバーフローする可能性はありますか？ 提示された制約下ではありません。より大規模な本番環境の規約では、上限を計算し、必要に応じて
bigintまたはより大きな整数型を使用する必要があります。 - 線形時間が必要ですか？ はい。
O(n^2)のベースラインは導出やテストには有用ですが、目標とする制約に対しては不十分です。
30秒の回答フレームワーク
「高さ h のバーに対して、その最も広い有効な長方形は、左右それぞれの最初のより低いバーの直前で終わります。私は、厳密に高さが 増加する順序でペア (start, height) を保持するスタックを用いて左から右へ走査します。現在の高さがスタックのトップより低い場合、現在のインデックスはそのトップのバーの 右側における最初のより低い境界となるため、それをポップして height * (right - start) を計算します。現在のより低いバーは、直前に削除されたすべての より高いバーにわたって拡張できるため、ポップされた start を左側に引き継ぎます。高さが等しい場合は、より前のエントリを保持します。末尾の仮想の 0 により、 残りのすべての長方形が確定します。各エントリは高々1回プッシュおよびポップされるため、時間計算量と補助空間計算量は O(n) および O(n) です。」
ステップバイステップの詳細解説
ステップ 1: 正しいベースラインを確立する。
すべての区間 [left, right] について、その最小の高さを追跡します。その最大の全幅長方形の 面積は次のとおりです：
min(heights[left..right]) * (right - left + 1)現在の最小値を維持しながら right を拡張すると、O(n^2) 時間、O(1) 空間の オラクルが生成されます。これは n = 100000 に対しては遅すぎますが、小さなランダム入力に対して最適化された解法をチェックするのには 極めて優れています。
ステップ 2: 列挙の視点を逆転させる。
すべての区間の最小値を求める代わりに、あるバーを長方形の制限となる 高さとして選択します。最も近い厳密により低い位置が leftShorter および rightShorter である場合、そのバーが カバーできる範囲は以下のようになります：
(leftShorter + 1) .. (rightShorter - 1)
width = rightShorter - leftShorter - 1これが、その制限の高さに対する最も広い長方形です。全体としての答えは、これらすべての 候補における最大値となります。
ステップ 3: 未解決のバーを昇順で保持する。
スタックには { start, height } を格納します。高さは厳密に増加します。start は、以前に確定して削除されたすべての より高いバーを取り除いた後、その高さが有効であり続けている最も早いインデックスです。 新しいより高いバーは自身のインデックスから始まります。新しいより低いバーは、より高いエントリを確定させ、ポップされた最も早い開始位置を 継承します。
[2, 1, 5, 6, 2, 3] の場合、インデックス 4 の高さ 2 は、まず 6 をポップして 6 * 1 を生成し、次に 5 をポップして 5 * 2 = 10 を生成します。高さ 2 はその2つのより高いバーをカバーできるため、開始位置 2 を継承します。 既存の高さ 1 はその下に残り、それ以上の左側への拡張を停止させます。
ステップ 4: 等価性と完了の定義。
現在の高さがスタックトップの高さと等しい場合は、古い方のエントリを保持します。2つのバーは同じ 高さを提供しますが、古い方のバーはより早い開始位置を持っているため、最良の長方形がより狭くなることは 決してありません。インデックス n の仮想の高さ 0 は、入力を変更したり クリーンアップロジックを重複させたりすることなく、すべての正のエントリを確定（クローズ）します。
ステップ 5: 不変条件の実装とポップ計算の証明。
interface StackBar {
start: number
height: number
}
export function largestRectangleArea(heights: number[]): number {
const stack: StackBar[] = []
let maxArea = 0
for (let right = 0; right <= heights.length; right += 1) {
const height = right === heights.length ? 0 : heights[right]
let start = right
while (stack.length > 0 && stack[stack.length - 1].height > height) {
const bar = stack.pop()!
maxArea = Math.max(maxArea, bar.height * (right - bar.start))
start = bar.start
}
const top = stack[stack.length - 1]
if (height > 0 && (!top || top.height < height)) {
stack.push({ start, height })
}
}
return maxArea
}この証明は、各走査ステップの前における3つの不変条件に基づいています：
- スタックの高さは厳密に増加している。
- 各エントリについて、
startからright - 1までの処理済みバーはすべて、少なくともその高さ以上である。 - その区間内には、厳密により低い処理済みバーは存在しない（存在する場合、そのエントリはすでにポップされているはずであるため）。
より小さい高さが出現したとき、不変条件 2 と 3 により、ポップされたエントリは right - 1 まで拡張できることが示され、現在のバーにより right まで拡張できないことが証明されます。したがって、その最大幅は 正確に right - start となり、計算された面積は完全です。現在の高さは削除されたすべての高さよりも小さいため、ポップされた開始位置を現在の 高さに引き継ぐことは安全です。保持された等しいエントリの開始位置はそれより遅くないため、等しい 高さをスキップすることは安全です。番兵は、右側にそれより低い実際のバーが存在しないすべてのエントリを確定します。したがって、考えられるすべての制限の高さについてその最大 長方形が考慮され、maxArea が最適解となります。
ステップ 6: エッジケースと計算量の検証。
異なる不変条件を検証する固定ケースを使用します：
| 入力 | 期待される出力 | チェック内容 |
|---|---|---|
[] | 0 | 文書化された空入力拡張 |
[2, 1, 5, 6, 2, 3] | 10 | 複数回のポップと継承された開始位置 |
[2, 4] | 4 | 単一バーでの最良解と右端のフラッシュ |
[2, 2, 2] | 6 | 重複する高さで最も早い開始位置を保持 |
[5, 4, 3, 2, 1] | 9 | 各ステップでの繰り返しのポップ |
[1, 2, 3, 4] | 6 | 番兵による増加スタックのフラッシュ |
[0, 2, 0] | 2 | 0 による長方形の分離 |
より強力な根拠として、多数の小さなランダム配列においてスタックの結果を二次時間のオラクルと比較します。上記の実装は、7つの固定ケースと、 長さ 0..8、高さ 0..7 の 20,000 個のランダム配列に対してチェックされました。これは実行可能な根拠であり、証明の代替ではありません。 不変条件が考えられるすべての入力を網羅的に説明します。
各正の高さは高々1回プッシュされ、高々1回ポップされるため、合計時間は O(n) です。 厳密に増加する入力では、番兵まで n 個すべてのエントリが保持され、最悪ケースの 補助空間計算量は O(n) となります。
質の高い模範解答
「まず二次時間のオラクルを確立します。各左境界に対して右境界を拡張し、最小の高さを維持します。これは考えられるすべての区間をチェックしますが、100,000 個の バーに対しては遅すぎます。繰り返し生じる問いは、選んだ高さがより低いバーに遮られるまでにどこまで拡張できるかということであり、これは最も近いより小さい境界と単調スタックの活用を示唆しています。
私のスタックは、未解決の各高さとともに有効な最も早い開始位置を保存し、その高さは 厳密に増加します。インデックス right では、トップが現在のバーより高い間ポップします。現在の インデックスはポップされたバーの最初の無効な位置であるため、その最大面積は bar.height * (right - bar.start) です。そのより低いバーは直前に削除されたすべてのより高いバーをカバーできるため、その開始位置を現在の高さに引き継ぎます。高さがスタックトップと等しい場合は、重複をプッシュする代わりに より前のエントリを保持します。末尾の仮想の 0 が残りのサフィックスを確定します。
スタック不変条件により、エントリの開始位置から現在の位置までのすべてのバーが十分な高さを 持っていることが保証されます。より低い現在のバーにより、計算された右境界が最終確定します。各エントリは高々1回 プッシュおよびポップされるため、時間計算量は O(n)、最悪ケースの空間計算量は O(n) となります。等しい高さ、 増加および減少配列、0、この拡張された仕様における空の入力をテストし、ランダムな小さなケースを二次時間のオラクルと比較します。」
よくある間違い
各失敗には特定の原因と修正方法があります：
- ポップの後に
right - start + 1を使用する →rightはすでに最初の無効な位置です →right - startを使用する。 - 最後のフラッシュを忘れる → 増加するサフィックスが評価されなくなります → 1つの仮想の 0 を走査する。
- 等しい高さをすべてプッシュする → 正当性がより繊細なポップルールに依存することになります → 最も早い等しいエントリを保持する。
- 内側のループによって時間が二次になると主張する → 各エントリは1回しかポップできません → ならし計算回数を提示する。
heightsに番兵を追加（append）する → 呼び出し元で変更（破壊）が観測されてしまいます → 番兵を仮想的に計算する。
発展的な深掘り質問
発展質問 1: 長方形の境界を返すにはどうすればよいですか？
面積が改善されるたびに、{ start: bar.start, end: right - 1, height: bar.height } を保存します。コーディング前に タイブレークを定義してください：最も左の長方形、最も広い長方形、または最も高い長方形を優先します。 面積だけでは一意の答えは決まりません。
発展質問 2: バーの幅が可変の場合はどうなりますか？
インデックスの幅を物理的な幅の累積和に置き換えます。スタックエントリは最も早い 水平座標を保持する必要があり、ポップされた面積は height * (currentX - startX) になります。幅 0 のバーや 無効な負の幅には明示的な規約が必要です。
発展質問 3: これはどのようにバイナリ行列に拡張されますか？
各行をヒストグラムの底辺として扱います。各列について、現在のセルが 1 のときはその高さをインクリメントし、 それ以外の場合は 0 にリセットします。各行の後にヒストグラムアルゴリズムを実行します。m × n の 行列の場合、時間計算量は O(mn)、補助空間計算量は O(n) です。
発展質問 4: ストリームに対して正確な答えを維持できますか？
スタックはバーをオンラインで処理できますが、ストリームの右端でまだ開いている長方形は 確定していません。スナップショットは、ポップすることなく現在の長さを使用してそれらの一時的な面積を計算できます。 厳密に増加するストリームでは正確な状態が O(n) まで増大する可能性があり、固定メモリでの正確な アルゴリズムはこの不変条件からは得られません。
発展質問 5: 入力が1台の気機のメモリに対して大きすぎる場合はどうなりますか？
最適な長方形がチャンクの境界をまたぐ可能性があるため、独立したチャンクごとの最大値だけでは不十分です。 分散サマリーは、隣接するチャンクをマージするために十分な境界の高さ構造を保持する必要があり、 単調なチャンクではそれ自体が線形になる可能性があります。サイズ固定のマージサマリーを約束する前に、その下限のリスクを言及してください。
発展質問 6: 別のアプローチが好ましいのはどのような場合ですか？
二次時間のオラクルは、小さな入力の検証に最適です。最小値を中心とした分割統治法は 漸化式を導出するのに有用ですが、各最小値に対する線形走査はソート済み入力で O(n^2) になります。Range Minimum Query（RMQ）データ構造は他の反復クエリをサポートできますが、この単一の 静的な最大値に対しては、単調スタックの方がシンプルで漸近的に最適です。