C++で解く「次のより大きい要素 III」（Next Greater Element III）の実装方法

32ビットの正の整数 n が与えられたとき、n とまったく同じ数字の並びを持ち、かつ n よりも大きい値となる最小の32ビット整数を求めます。そのような整数が存在しない場合は -1 を返します。

例えば、入力が 213 の場合、同じ数字を使って作れるより大きい数のうち最小のものは 231 なので、答えは 231 になります。

解法のアプローチ

この問題は、いわゆる「次の順列（next permutation）」を求めるアルゴリズムと同じ考え方で解くことができます。手順は以下の通りです。

• s := n を文字列に変換したもの、sz := s の長さ、ok := false と初期化する
• i を sz - 2 から 0 まで降順に走査する。もし s[i] < s[i + 1] が成り立てば、ok := true としてループを抜ける
• ok が false のままなら、桁がすべて降順に並んでいる（これより大きい並べ替えが存在しない）ため、-1 を返す
• smallest := i、curr := i + 1 とする
• j を i + 1 から sz - 1 まで走査し、s[j] > s[smallest] かつ s[j] <= s[curr] を満たすたびに curr := j と更新する
• s[smallest] と s[curr] を入れ替える
• aux := s のインデックス smallest + 1 以降の部分文字列とし、aux を反転する
• ret := s の先頭から smallest までの部分文字列に aux を連結したものとする
• ret が32ビット正整数の範囲を超えていれば -1 を、そうでなければ ret を返す

このアルゴリズムのポイントは、右端から見て最初に「左の数字が右の数字より小さい」位置を見つけ、その位置の数字を、右側に残った数字の中で「その数字より大きい最小の数字」と入れ替え、残りを昇順に並べ直す（反転操作で実現できる）ことです。これにより、桁数を d とすると O(d) の計算量で次に大きい数を効率的に求められます。

実装例

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

Example

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int nextGreaterElement(int n) {
        string s = to_string(n);
        int sz = s.size();
        int i;
        bool ok = false;
        for(i = sz - 2; i >= 0; i--){
            if(s[i] < s[i + 1]) {
                ok = true;
                break;
            }
        }
        if(!ok) return -1;
        int smallest = i;
        int curr = i + 1;
        for(int j = i + 1; j < sz; j++){
            if(s[j] > s[smallest] && s[j] <= s[curr]){
                curr = j;
            }
        }
        swap(s[smallest], s[curr]);
        string aux = s.substr(smallest + 1);
        reverse(aux.begin(), aux.end());
        string ret = s.substr(0, smallest + 1) + aux;
        return stol(ret) > INT_MAX ? -1 : stol(ret);
    }
};
main(){
    Solution ob;
    cout << (ob.nextGreaterElement(213));
}

入力

213

出力

231