题目

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();// 从后向前遍历字符串 sfor (int i = s.size() - 1; i >= 1; i --){// 如果前一个字符大于当前字符，说明不满足单调递增的条件if (s[i - 1] > s[i]) {s[i - 1] --; // 将前一个字符减 1flag = i; // 记录需要修改为 '9' 的起始位置}}// 从 flag 开始，将后面的字符全部修改为 '9'for (int i = flag; i < s.size(); i ++) s[i] = '9';// 将字符串 s 转换回整数并返回return stoi(s);}
};