C++で配列がスタックソート可能かどうかを判定する方法

1からnまでの一意な要素で構成される配列 nums があるとします。この配列が「スタックソート可能」であるかどうかを判定する必要があります。スタックソート可能とは、一時的なスタックを介して別の配列へ要素を移動させたとき、結果の配列が非減少順（昇順）に並べられることを指します。

この問題を解くには、元の配列に対して次の2つの操作を任意の回数実行できます。

• 配列の先頭要素を削除し、その要素をスタックにプッシュする。
• スタックのトップ要素を取り出し（ポップし）、2番目の配列の末尾に挿入する。

これらの操作によって元の配列の全要素を2番目の配列へ移動でき、その結果が昇順にソートされていれば、元の配列はスタックソート可能であるといえます。

例えば、入力が nums = [8, 6, 5, 3, 1] の場合、出力は True になります。すべての要素をスタックに積んだ後、ポップしていくと [1, 3, 5, 6, 8] という昇順の配列が得られるためです。

アルゴリズムの手順

この問題は以下の手順で解決できます。

• スタック stk を定義する。
• last := 0 と初期化する（last は出力済みの最大値を表す）。
• i := 0 から配列 v のサイズ未満の間、i を1ずつ増やしながら以下を繰り返す。
  • stk が空でない場合：
    • top := stk のトップ要素とする。
    • top == last + 1 である間、次を繰り返す。
      • last := last + 1 とし、stk からポップする。
      • stk が空になったらループを抜ける。
      • top := stk のトップ要素を更新する。
    • stk が空であれば、v[i] を stk にプッシュする。
    • そうでなければ、top := stk のトップ要素とし、v[i] < top なら v[i] をプッシュ、そうでなければ false を返す。
  • stk が空の場合は、v[i] を stk にプッシュする。
• 最後に true を返す。

アルゴリズムのポイント

このアルゴリズムでは、新しい要素が現在のスタックのトップより小さい場合にのみプッシュを許可しています。これにより、スタック内では常に下から上に向かって値が減少することが保証され、最後にすべてをポップすれば昇順の配列が得られます。もし新しい要素がトップ以上であれば、後から正しい順序で取り出せないため false を返します。また、トップが last + 1（次に出力すべき値）と一致するときは、すぐにポップして出力側へ移せるため、その処理を優先的に行っています。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> &v) {
    stack<int> stk;
    int last = 0;
    for (int i = 0; i < v.size(); i++) {
        if (!stk.empty()){
            int top = stk.top();
            while (top == last + 1) {
                last = last + 1;
                stk.pop();
                if (stk.empty()){
                    break;
                }
                top = stk.top();
            }
            if (stk.empty()) {
                stk.push(v[i]);
            } else {
                top = stk.top();
                if (v[i] < top){
                    stk.push(v[i]);
                } else {
                    return false;
                }
            }
        } else {
            stk.push(v[i]);
        }
    }
    return true;
}
main(){
    vector<int> v = {8, 6, 5, 3, 1};
    cout << solve(v);
}

入力

{8, 6, 5, 3, 1}

出力

1