🚩传送门：https://leetcode-cn.com/problems/monotone-increasing-digits/
题目
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
示例 1:
输入: N = 10 输出: 9
示例 2:
输入: N = 1234 输出: 1234
示例 3:
输入: N = 332 输出: 299
说明: N 是在 [ 0, 109 ] 范围内的一个整数。
题意解释：整个数字要符合依次递增
图示思路：
图1【 从1开始 】 图2【 不符合**前小后大 **】 图3【 **i后退，str[i-1]减1 **】<br />  
图4 【重复图3的过程】 图5【极限情况，i一路后退至0】
解题思路：贪心
官方文档：给定是贪婪，暂时不清楚贪在哪里。
- 将 int 类型转换为 String 类型 （目的便于当作数组计算）
- 首先从下标 1开始，一直遍历到 N ( 数字个数 )直至不符合【前小后大】为止。即如 图1 图2 所示
- if ( str [ i ] >= str [ i-1 ] ) 则 i++ 【即后面的数字大于前面的数字，则继续向后遍历】即 图1 向 图2的过程
- else { str[i-1]-=1 ，i-=1} 【即后面数小于前面的数字，所以前面数字先减一看是否还能满足比前面数字大】即图 3所示
- 如果持续不满足前大后小，则重复过程2,直至满足或者 i 为0
- 如果 i 持续后退减1直至 i =0 ，则后面数字一律用9填
- 如果后退的中途减 1满足了前大后小，则 i 后面的数字用9填充。
官方代码
# include<iostream># include<string>using namespace std;int monotoneIncreasingDigits(int N) {string str = to_string(N);int i = 1; //从1开始遍历直至末尾N结束while (i < str.length()&& str[i] >= str[i - 1]) {//目的:找出第一个不符合前小后大的数字//i在范围内，并且满足后大前小，则i++i++;}//出第一个while有两种可能，要么到了末尾，整个数组全满足，要么中途出现不满足if (i == str.length()) {//整个数组满足,数组输出即可;//啥也不需要做}else {//中途不满足,出现了前大后小情形while (i>0&&str[i] < str[i - 1]) {//目的:找到最终的回退点str[i - 1] -= 1;//前数减1i--;//下标后退}i++;//是从满足前小后大的数字开始后面置9}while (i < str.length()) {str[i] = '9';i++;}return stoi(str);}int main(void) {cout << monotoneIncreasingDigits(120) << endl;system("pause");return 0;}
若有收获，就点个赞吧
0 人点赞
