0Pricing
Coding Interview Prep · レッスン

単調スタック: 次に大きい要素

1 回の走査で区間クエリに答えます

「単調スタック: 次に大きい要素」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

次に大きい要素の問題

各数値について、右側にある最初のより大きな値を求めます。全探索では O(n 二乗) ですが、単調スタックなら一度の走査で解けます。

単調とは何か

単調スタックは値を並び順、ここでは降順に保ちます。その順序が崩れる瞬間に、答えが見つかったと判断できます。

値ではなくインデックスを保存する

数値そのものではなくインデックスをプッシュします。そうすれば、より大きな要素が現れたときに、どの位置を埋めるべきか正確に分かります。

stack = []
ans = [-1] * len(nums)

左から右へ走査する

配列を一度だけループします。各インデックスで、解決済みの要素をポップするか、後で処理するために現在のインデックスをプッシュします。

for i in range(len(nums)):

小さい要素をポップする

現在の値が先頭インデックスの値より大きい間、その先頭の要素には次に大きい要素が見つかったことになります。

    while stack and nums[i] > nums[stack[-1]]:

答えを記録する

先頭のインデックスをポップし、その答えを現在の値に設定します。各インデックスは一度だけ解決されるため、処理量は線形に保たれます。

        j = stack.pop()
        ans[j] = nums[i]

プッシュして続ける

それより小さい要素をすべて解決したら、現在のインデックスをプッシュします。これで、将来現れるより大きな要素を待てます。

    stack.append(i)

残った要素には答えがない

最後までスタックに残ったインデックスは、より大きな値に出会っていません。答えの初期値である -1 のままになり、該当する要素がないことを表します。

なぜ O(n) なのか

各インデックスは一度プッシュされ、一度ポップされるだけです。内側に while ループがあっても、全体の走査にかかる処理量は線形になります。

次に小さい要素に応用する

次に小さい要素が必要な場合は、比較を大なりから小なりに反転し、スタックを昇順に保ちます。

    while stack and nums[i] < nums[stack[-1]]:

小技ではなくパターン

区間クエリ、株価、ヒストグラムの面積などで、この考え方を再利用できます。単調スタックは、覚えておく価値のあるコンテストの基本パターンです。

確認問題

単調スタックで次に大きい要素を求めます。全体の実行時間が線形になるのはなぜでしょうか。

まとめ：一度の走査で多くの答えを求める

インデックスの降順の単調スタックを使い、O(n) で次に大きい要素を求めました。このパターンによって、多くの区間問題を解けるようになります。🚀

よくある質問

「単調スタック: 次に大きい要素」レッスンは無料ですか？

はい。「単調スタック: 次に大きい要素」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「単調スタック: 次に大きい要素」で何を学びますか？

1 回の走査で区間クエリに答えます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「単調スタック: 次に大きい要素」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 括弧の対応確認に使うスタック
  2. 単調スタック: 次に大きい要素
  3. キューと collections.deque
  4. Deque によるスライディングウィンドウ最大値
← Coding Interview Prepに戻る