Next Greater Element III หาตัวเลขถัดไปใน C++

ให้จำนวนเต็มบวก 32-bit n หาตัวเลข 32-bit ที่น้อยที่สุดซึ่งมีหลักตัวเลขเหมือน n ทุกประการแต่มากกว่า n หากไม่มีให้คืน -1

ตัวอย่าง: 213 → 231

วิธีแก้ปัญหา (Next Permutation Logic)

1. แปลง n เป็นสตริง s, sz = ความยาว, ok = false
2. วน i จาก sz-2 ลง 0:
   • ถ้า s[i] < s[i+1] → ok = true, break
3. ถ้า !ok → คืน -1
4. smallest = i, curr = i+1
5. วน j = i+1 ถึง sz-1:
   • ถ้า s[j] > s[smallest] และ s[j] ≤ s[curr] → curr = j
6. สลับ s[smallest] กับ s[curr]
7. aux = substring จาก smallest+1 ถึงสุด, แล้ว reverse aux
8. ret = substring 0 ถึง smallest + aux
9. ถ้า ret > INT_MAX → -1 มิฉะนั้น ret

ตัวอย่างโค้ด C++

#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);
    }
};

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

Input

213

Output

231