algo-aha

数字递增的<=N的数

• https://leetcode.com/problems/monotone-increasing-digits/

int monotoneIncreasingDigits(int N) {
    // 将N的串表示从右往左不断将逆序波峰值减1，
    // 然后将最左逆序波峰后面的所有数字都变为9
    string s = to_string(N);
    int pos = s.size();
    for (int i = s.size() - 2; i >= 0; i--) {
        if (s[i] > s[i+1]) {
            s[i]--;
            pos = i;
        }
    }
    for (int i = pos + 1; i < s.size(); i++) {
        s[i] = '9';
    }
    return stoi(s);
}