Số lớn hơn tiếp theo với cùng chữ số (Next Greater Element III) trong C++

Cho số nguyên dương 32-bit n, tìm số 32-bit nhỏ nhất lớn hơn n có cùng tập chữ số. Nếu không tồn tại trả về -1.

Ví dụ: 213 → 231.

Thuật toán (Next Permutation)

1. Chuyển thành chuỗi s.
2. Tìm chỉ số i từ phải sang trái sao cho s[i] < s[i+1].
3. Nếu không tìm thấy → trả về -1.
4. Tìm chỉ số j > i nhỏ nhất sao cho s[j] > s[i] (chọn j cuối cùng thỏa mãn).
5. Hoán đổi s[i] và s[j].
6. Đảo ngược đoạn sau i.
7. Chuyển về số, kiểm tra vượt 32-bit.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int nextGreaterElement(int n) {
        string s = to_string(n);
        int sz = s.size(), 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, 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;
        long val = stol(ret);
        return val > INT_MAX ? -1 : val;
    }
};

int main() {
    Solution ob;
    cout << ob.nextGreaterElement(213);
    return 0;
}

Đầu vào / Đầu ra

Input: 213

Output: 231