Số có chữ số tăng dần đơn điệu trong C++

Cho một số nguyên không âm N, tìm số lớn nhất nhỏ hơn hoặc bằng N sao cho các chữ số của nó tăng dần đơn điệu (mỗi cặp chữ số liền kề x, y thỏa mãn x <= y).

Ví dụ: N = 332 → kết quả 299.

Thuật toán

1. Chuyển N thành chuỗi s, đặt i = 1, n = s.length().
2. Tăng i cho đến khi s[i] < s[i-1] hoặc hết chuỗi.
3. Nếu i < n:
   • Lùi i về trước và giảm s[i] đi 1 cho đến khi s[i-1] <= s[i].
4. Đặt tất cả ký tự từ i+1 đến cuối thành '9'.
5. Chuyển chuỗi kết quả về số nguyên.

Mã nguồn C++

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

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string s = to_string(N);
        int i = 1, n = s.size();
        while (i < n && s[i] >= s[i-1]) i++;
        if (i < n) {
            while (i > 0 && s[i-1] > s[i]) {
                i--;
                s[i]--;
            }
        }
        for (int j = i+1; j < n; j++) s[j] = '9';
        return stoi(s);
    }
};

int main() {
    Solution ob;
    cout << ob.monotoneIncreasingDigits(332);
    return 0;
}

Đầu vào / Đầu ra

Input: 332

Output: 299