面接官が評価するポイント
循環する整数配列が与えられたとき、各要素について時計回りに最初に現れる自身より真に大きい値を返します（存在しない場合は -1 を返します）。入力には重複要素、単調な並び、またはすべての値が同一である配列が含まれる場合があります。
制約条件と境界条件
- 「より大きい（Greater）」は厳格（strict）です。等しい値ではインデックスを確定できません。
- インデックス
iはi+1からn-1まで探索し、その後0へと循環（ラップアラウンド）します。 - 各位置に設定される答えは最大1つです。2周目の走査ですでに確定した結果を上書きしてはなりません。
- 目標は O(n) の時間計算量と O(n) の追加空間計算量です。
30秒で答えるフレームワーク
「自身より大きい値をまだ待っているインデックスを保持する減少スタックを使用します。仮想的に2倍にした配列を走査します。現在の値がスタックトップより真に大きければ、スタックのエントリをポップして答えを確定させます。インデックスのプッシュは1周目のみ行い、2周目は循環用の候補値の供給としてのみ使用します。各インデックスのプッシュとポップはそれぞれ最大1回であるため、アルゴリズムは線形時間で動作します。」
答えを待つ位置（インデックス）を保持する
結果を直接書き込み、重複する値の位置を区別できるように、値そのものではなくインデックスを保持します。スタックの底からトップにかけて値が非増加（広義の単調減少）となる状態を維持します。現在の値がより大きければ、ポップ可能な自身より小さいすべての待機値を確定させます。
循環を限定的な走査に変換する
0 から 2n-2 までの i に対し、nums[i % n] を読み取ります。i が n 未満の場合は、スタック内の古いエントリを確定させた後にそのインデックスをプッシュします。2周目の訪問時は、残りのスタックを確定させるためだけに使用します。これにより配列のコピー作成を避け、無限ループを防ぐことができます。
厳格な比較と重複要素の処理
nums[current] > nums[stackTop] の場合にのみポップします。「以上（greater-than-or-equal）」にしてしまうと、等しい値同士で誤って解決してしまいます。また「未満（less-than）」では減少の不変条件が崩れます。未解決のインデックスには初期値の -1 がそのまま保持されます。
回答前に確認すべき質問
- 「次の値」は厳格により大きい（strictly greater）必要がありますか？「以上」を許容する場合、ポップ条件と重複時の挙動が変わります。
- 配列が空になることはありますか？実装前に戻り値の形式を定義します。
- 結果として返すのは値ですか、それともインデックスですか？距離やインデックスを返す場合は、循環時の計算方法が異なります。
ステップごとの詳細解説
すべての結果を -1 に初期化し、空のスタックを用意します。仮想位置 i に対して index = i % n を設定し、value = nums[index] を読み取ります。まず、現在の値より小さい値を持つスタック内のインデックスを確定させます。i が n 未満のときは、まだ時計回りの探索が1周完了していないため、index をプッシュします。2周目は決してプッシュを行わないため、すべてのインデックスが入るのは1度だけです。
result = [-1] * n
stack = []
for i in range(2 * n - 1):
index = i % n
while stack and nums[stack[-1]] < nums[index]:
result[stack.pop()] = nums[index]
if i < n:
stack.append(index)[1,2,1] の場合、末尾の 1 は循環した後に 2 を見つけますが、2 には自身より真に大きい値が存在しません。スタックに残ったインデックスは正しく -1 を維持します。
模範解答の例
「まだ答えが見つかっていないインデックスを非増加スタックに格納します。i % n を用いて配列を論理的に2回走査します。スタックトップより真に大きい現在の値が現れたら、そのインデックスをポップして答えを確定させます。各インデックスは最初の走査時のみプッシュするため、2回目の走査では重複なしで循環処理を行えます。結果配列を -1 で初期化しておくことで、すべての要素が同じ配列や答えが存在しない場合も正しく処理されます。すべてのインデックスは最大1回プッシュされ最大1回ポップされるため、時間計算量は O(n)、空間計算量は O(n) となります。」
よくある間違い
- 循環を処理するために配列を3回コピーしてしまう。
- 2周目でもインデックスをプッシュしてしまい、重複処理や結果の上書きが発生する。
- 「以上」を使用してしまい、等しい値を「より大きい」として処理してしまう。
- スタックの不変条件を定義せずに右から走査し、答えが「最初に現れるより大きい値」にならなくなってしまう。
- 結果を初期化せず、走査後にスタックを無理に修復しようとする。
不具合の兆候と修正方法
[1,1,1] に対して -1 以外の値が返る場合、等価性の判定ルールが間違っています。[1,2,1] の最後の 1 が -1 を返す場合、循環処理が抜けています。スタックのインデックスと値をトレースし、すべてのポップ処理において現在の値が真に大きいことをアサートしてください。
プロダクションコードにおける実装の注意点
入力に対して十分な幅を持つインデックス型を使用してください。メモリに制約がある場合は配列のコピーを避けます。距離を返す場合は、インデックス j を確定する際に (index - j + n) % n を計算し、距離0が許容されるかどうかを定義してください。
検証チェックリスト
空の入力、要素数1、全要素が同一、狭義の単調増加、狭義の単調減少、複数のピーク値が存在する配列、およびランダムな配列でテストします。小さな入力に対しては、ランダム差分テストを用いて各インデックスから時計回りに走査する O(n²) のリファレンス実装と比較します。
フォローアップ質問と回答
なぜ各インデックスは1回しかポップされないのですか？
インデックスは、時計回りで最初に現れる真に大きい値を見つけた時点でスタックから取り除かれます。それ以降の要素が「最初のより大きい値」になることはありません。各インデックスは1回プッシュされ1回ポップされるため、ポップ処理全体の計算量は O(n) です。
「以上」を求める場合は何が変わりますか？
現在の値がスタックトップの値以下である場合にポップするようにし、配列を循環する際の等しい値の扱い（後の周回で自分自身によって解決されることを許容するかどうかなど）を定義する必要があります。
入力が無限に繰り返されるストリームの場合はどうしますか？
すべての位置が解決するのを待ち続けることはできません。有限の観測ウィンドウまたはタイムアウトを設定します。固定長配列の場合、2周の走査ですべての将来的な候補をカバーできます。
評価基準
- 不変条件：減少スタックが答えを待っているインデックスを保持していることを説明できているか。
- 循環処理：コピーや無限ループを行わず、2周の限定走査を用いているか。
- 重複の境界条件：厳格な比較を使用し、未解決の
-1値を保持できているか。 - 計算量：O(n) の時間計算量と O(n) の追加空間計算量を提示できているか。
- 検証：O(n²) のオラクル、およびランダム・重複・単調テストを網羅しているか。
適合性チェック
スタックの不変条件、循環の境界条件、および計算量の主張が一貫していることを確認してください。
面接回答チェックリスト
スタック内のインデックスがより大きい値を待っていることを述べ、i % n、2周走査、厳格なポップ条件、インデックスあたり1回のプッシュ、ならびにならし計算量について説明します。
1行のまとめ
循環配列における Next Greater クエリは、2周のインデックス走査と単調減少スタックにより線形時間で解決でき、厳格な比較と -1 による初期化によって重複要素および解なしのセマンティクスが正しく保持されます。