题目

738. 单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1:

输入: n = 10

输出: 9

示例 2:

输入: n = 1234

输出: 1234

示例 3:

输入: n = 332

输出: 299

来源：力扣738. 单调递增的数字

思路（注意事项）

思路就是从后往前遍历，将遍历到的元素s[i]与该元素的前一个元素s[i - 1]比较，如果前一个元素大于该元素则将前一个元素 - 1，同时将该元素s[i]置为9，依次类推。实际写代码中，用一个flag位标记需要修改为9的所有位置。

纯代码

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n);
        int flag = s.size();
        for (int i = s.size() - 1; i >= 1; i --)
        {
            if (s[i - 1] > s[i]) 
            {
                s[i - 1] --;
                flag = i;
            }
        }

        for (int i = flag; i < s.size(); i ++) s[i] = '9';
        return stoi(s);
    }
};

题解（加注释）

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        // 将整数 n 转换为字符串 s，方便逐字符处理
        string s = to_string(n);
        // flag 用于记录需要修改为 '9' 的起始位置
        int flag = s.size();

        // 从后向前遍历字符串 s
        for (int i = s.size() - 1; i >= 1; i --)
        {
            // 如果前一个字符大于当前字符，说明不满足单调递增的条件
            if (s[i - 1] > s[i]) 
            {
                s[i - 1] --; // 将前一个字符减 1
                flag = i; // 记录需要修改为 '9' 的起始位置
            }
        }

        // 从 flag 开始，将后面的字符全部修改为 '9'
        for (int i = flag; i < s.size(); i ++) s[i] = '9';

        // 将字符串 s 转换回整数并返回
        return stoi(s);
    }
};