面接官が見ているポイント
重複を含む可能性がある整数配列が与えられたとき、それをインプレースで辞書順で真に次に大きい順列へと変更します。現在の並びが最大である場合は、最も小さい昇順の順列を生成します。
制約と境界条件
- O(1) の追加空間のみを使用し、交換（swap）または反転（reverse）のみを行います。
- 重複する値は区別された個体ではありませんが、比較は数値として行われます。
- 空の配列および要素が1つの配列は変更されません。
- 結果は任意の局所的な交換ではなく、大域的に隣接する辞書順の順列でなければなりません。
最も右側にあるピボットを見つける
右側から走査し、左側の値が右側の値よりも真に小さい最初のインデックス i を探します。サフィックス（接尾辞）はすでに非増加（降順）になっています。ピボットが存在しない場合、配列全体が最大の状態であるため、配列全体を反転して最小の順列を取得します。
交換してサフィックスを最小化する
ピボットが見つかったら、右側から走査して nums[i] より大きい最初の値を探します。サフィックスは非増加であるため、その最初の候補が実行可能な最も小さい「より大きい値」になります。それをピボットと交換し、i より後のサフィックスを反転して昇順にします。
30秒の回答フレームワーク
「右側から走査して、最初に増加するピボット i を探します。存在しない場合は、最大状態である降順配列を反転します。存在する場合は、nums[i] より大きい最も右側の値を見つけてそれらを交換し、サフィックスを反転します。サフィックスは最初は逆方向に整列しているため、これにより時間計算量 O(n)、空間計算量 O(1) で可能な限り最小の増加を実現できます。」
回答前の明確化のための質問
- 変更はインプレースで行う必要がありますか？追加空間が許可されるならコピーをソートできますが、インプレースの場合は反転が必要です。
- 辞書順は数値ベースですか、それとも文字列ベースですか？負の数や複数桁の値で結果が異なります。
- 値は重複することがありますか？重複がある場合、ピボットおよび交換候補の両方で厳密な比較が必要になります。
ステップごとの詳細解説
[1,2,3] の場合、1 のピボットはサフィックス内のより大きい最小値である 2 と交換され、サフィックスを反転した後に [2,1,3] となります。[3,2,1] の場合はピボットが存在しないため、反転によって [1,2,3] が生成されます。
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = n - 1
while nums[j] <= nums[i]:
j -= 1
swap(nums[i], nums[j])
reverse(nums, i + 1, n - 1)ピボット候補をスキップする際は「以上」、交換候補をスキップする際は「以下」を使用し、真の増加を保証します。サフィックスはすでに整列しているため、ソートではなく反転を使用することで、線形時間かつインプレースの処理を維持できます。
模範的な高品質の回答
「次の順列は、可能な限り最も右側の位置を変更し、それ以降のすべてを可能な限り小さくすることです。左側の値が右側の値より真に小さい最も右側のピボットを見つけ、それより大きい最も右側の値と交換し、サフィックスを反転します。ピボットがない場合は配列が最大であることを意味するため、配列全体を反転します。走査と反転は O(n) であり、アルゴリズムは定数個の追加変数のみを使用します。」
よくあるミス
- 左側からピボットを探してしまい、より上位の桁の位置を変更してしまう。
- サフィックスを最小化せずに、交換後に処理を終了してしまう。
- 交換候補に対して「以上」を使用してしまい、重複がある場合に真の増加とならない。
- サフィックスに対して一般的なソートを呼び出し、インプレースの制約に違反してしまう。
- 最小の順序に巻き戻すべきときに、降順配列を変更せずにそのまま返してしまう。
失敗の兆候と修正方法
[1,3,2] が [3,1,2] になる場合、ピボットが左によりすぎています。正しい結果は [2,1,3] です。[1,1,5] が等しい値同士を交換してしまう場合、厳密な比較の境界条件が誤っています。
本番環境での実装
変更可能なランダムアクセスシーケンスを受け取り、2つのポインタで反転します。比較によってオーバーフローが発生する可能性がある場合や、言語の順序付けが異なる場合は、インターフェースの境界で比較関数や無効な入力に対するポリシーを定義します。
検証チェックリスト
空、1要素、昇順、降順、重複、末尾のピボット、および複数の同一の最適値を含む配列をテストします。小さな配列の場合は、すべての異なる順列を生成して辞書順にソートし、関数が次の要素を返すか、または最初の要素に巻き戻ることを検証します。
フォローアップの質問と回答
なぜピボットは最も右側のものでなければならないのですか？
より右側にあるピボットほど、より下位の桁の位置を変更することになります。したがって、実行可能な最も小さい「より大きい値」を選択してそのサフィックスを最小化することで、有効な順序をスキップすることなく隣接する順列が得られます。
なぜサフィックスを直接反転できるのですか？
右から左へのピボット走査により、サフィックスが非増加であることが証明されます。交換後、それを反転することで、一般的なソートを行わずに最小の昇順が復元されます。
k 番目に次の順列を求めるにはどうすればよいですか？
この操作を繰り返すと O(k n) のコストがかかります。k が大きい場合は、rank/unrank またはカウント手法によって直接ジャンプできますが、組合せのカウントと重複の処理が必要になります。
評価基準（ルーブリック）
- ピボット：最も右側の厳密な増加を正しく見つけているか。
- 交換：右側から最初の真に大きい値を選択しているか。
- サフィックス：それを反転して最小の昇順にしているか。
- 境界条件：降順、重複、空、および1要素の配列を網羅しているか。
- 計算量：時間計算量 O(n) および追加空間計算量 O(1) を提示しているか。
適合性チェック
3つのステップ、境界条件の例、および計算量の主張が一貫していることを確認します。
面接での回答チェックリスト
最も右側の最小限の変更について説明し、ピボット、交換、反転のコードを書き、厳密な比較のために重複の例を使用し、計算量と小さな順列での網羅的なテストを提示します。
一行のまとめ
次の順列は、最も右側のピボット、実行可能な最小の大きい値との交換、およびサフィックスの反転により、インプレースかつ線形時間で見つかります。