【LeetCode贪心#11】单调递增的数字（详解）
单调递增的数字
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
示例 1:
- 输入: N = 10
- 输出: 9
示例 2:
- 输入: N = 1234
- 输出: 1234
示例 3:
- 输入: N = 332
- 输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数
思路
题意解析
题目举的例子有点不太好理解，这里再举一个吧
- 输入: N = 32
- 输出: 29
什么意思呢？就是32这个输入数，其不满足各个位数上的数字是单调递增的规则
因此需要找一个比32小但是尽可能大的整数，该整数还要满足各个位数上的数字单调递增的规则
那么29显然是符合条件的
解法
用人脑想可以想到上面情况中29是符合条件的数，但是用算法怎么实现？
如果去遍历nums（32），可以得到nums[i]（2）小于nums[i - 1]（3）
此时出现了单调递减，不符合条件，需要去找比nums小的一个最大单调递增整数
怎么找？
因为32已经是单调递减了，所以个位上的2无论怎么变化都不能逆转递减的趋势，因此需要把十位减小使整体满足递减的要求，按照上述逻辑可以得到22
因为大于等于都算递增，所以此时的22已经满足单调递增的条件了，接下来需要达成最大整数这个条件
显然22不是小于32的数中满足单调递增的最大整数，在2X中找最大整数，那X只要取9就可以使整体最大，所以满足所有条件的数是29
总结一下：
? 当遍历遇到单调递减的两位数时，可以直接将十位数减1，然后个位取9，得到小于当前这两位数的最大单调递增整数
? 这里也可以确认 ，遍历时我们是两个两个数来判断是否符合条件的
遍历nums的顺序
问题又来了，遍历nums的顺序是什么呢？
先说结论，应该从后先前遍历
举个例子：
- 输入: N = 332
- 输出: 299
如果从前向后遍历，过程如下:
? 先得到33，33满足单调递增条件，不管
? 然后得到32，不满足条件，按照上面的逻辑找到小于32有满足条件的最大整数29，遍历结束
? 此时整体为329，还是不满足条件
? 原因是从前向后遍历没有将前面判断得到的结果利用起来
在来看从后向前遍历：
? 先得的32，不满足条件，修改为29，此时整体为329
? 然后得到32（基于前一步的结果），还是不满足条件，修改为29，此时整体为299，遍历结束
? 结果正确
修改9的逻辑
上面其实就是全部的解题逻辑了，但是按照上面的讨论去实现代码时会发现有问题，每次遇到单调递减的数时我们会下意识的直接把9给换到相应位置，但其实这样会出错
举个例子：
- 输入: N = 3232
- 输出: 2999
这个例子的正确答案是2999，如果在实现时按照上面的问题逻辑来的话，得到的结果会是2929
先不说它是不是最大的吧，它就不满足单调递增
因此我们需要一个变量，记录最后一次要改9的位置，然后将其后位置的所有数全部改成9
3 2 3 2
↑ ↑
i-1 i
i 处要改9，此时，flag == 3
3 2 3 2
↑ ↑
i-1 i
此时flag还是3
3 2 3 2
↑ ↑
i-1 i
i 处要改9，此时，flag == 1
遍历结束，将flag往后的所有数都改成9，得到正确结果2999
注意，flag的初始值应该指向数组末尾
代码
注意这里给的输入是一个int，要先把其转化为str才能遍历
然后改完记得再转回来（使用stoi函数）
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string strNum = to_string(n);
int flag = strNum.size();//flag初始值应该指向数组末尾
for(int i = strNum.size() - 1; i > 0; --i){
if(strNum[i - 1] > strNum[i]){//单调递减
strNum[i - 1]--;
// strNum[i] = '9';
flag = i;//记录要修改9的位置
}
}//遍历完成，找到要修改9的位置
for(int i = flag; i < strNum.size(); ++i){//将flag后的数全改为9
strNum[i] = '9';
}
int num = stoi(strNum);//转回int
return num;
}
};