738.单调递增的数字（暴力解也需要看一下）
- 本题暴力解法也需要看一下，虽然暴力解法超时了，但是这种思路是一种很基础的思路，需要了解
- 数字是没有办法直接采用下标遍历的，如果要for循环遍历每个位置的数字，需要把数字转成字符串string
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 10
输出: 9
示例 2:
输入: n = 1234
输出: 1234
示例 3:
输入: n = 332
输出: 299
提示:
- 0 <= n <= 10^9
暴力解写法
本题题意比较清晰，我们可以首先考虑用暴力来实现一下。也就是给我们一个数值，我们直接从大到小去遍历，并判断每个数值是不是单调递增的。
- 注意暴力解法不能直接操作i，直接操作i会导致for循环里i–的时候也受到影响！需要用单独的temp来存储i
- 暴力解法必须需要
bool isIncreasing的原因，是因为while里面break了之后依然会执行外层的for，也就是说会执行for剩下的代码逻辑！我们不能让break出来之后再continue，因此只能加上判断变量，break的情况就判断为false。确定判断为true的时候，才是结束了while循环的时候，此时再返回。
class Solution {
public:
int monotoneIncreasingDigits(int n) {
for(int i=n;i>=0;i--){
int max = INT_MAX;
int temp=i;
//定义判断变量
bool isIncreasing = true;
while(temp){//只要还有数字
int ten = temp%10;//先取最后一位
if(max>=ten) max=ten;
else{
isIncreasing = false;
break;//只要前一位不满足大于等于，就说明不是单调递增，记为false继续遍历下个数
}
temp=temp/10;//i减少一位
}
//结束while并且满足true,说明找到了
if(isIncreasing==true)
return i;
}
//最后没找到 return 0
return 0;
}
};
注意：必须引入isIncreasing变量的原因
暴力解法里面需要注意，当while循环中的break语句被执行时，它会立即终止当前正在进行的while循环，并且控制流将会继续从break语句跳出while之后，后面的for代码开始执行。这就意味着即使temp并不是单调递增的（在这种情况下，while循环会由于break语句而提前结束），for循环之后的代码也会被执行！这就可能导致不正确的结果被返回。
break只是跳出当前的循环，在while里面的时候，跳出的是while而不是最外层的for
为此，引入了isIncreasing变量。只有在temp是单调递增的情况下（即while循环正常结束，而不是由于break语句而提前结束），isIncreasing变量才会保持为true，并且正确的结果i会被返回。
这种解法逻辑正确，但是超时了。
贪心思路
我们以32来举例。如果两位不符合要求，前一位需要做-1处理！这样后一位才有大于前一位的可能。
那么前一位-1之后，后一位的值应该取最大的，才能让得到的数值最大！
因此32的十位-1得到2 个位取最大得到29。也就是说，遍历数字的时候，凡是前面一位>后面一位，都是前面一位做减一，后面一位取最大值（也就是9）
遍历顺序
以332来举例，如果从前往后遍历，遍历到第二个3的时候，就会发现后面的32换成29之后，整体不满足单调递增了
从前往后处理的话，因为涉及-1操作，所以后面得到的值，有可能比前面的值要小！会导致遍历到后面不满足单调递增！
而从后往前遍历的话，就可以考虑到前一位-1，对前面的数字单调递增特性造成的影响。
最开始的写法
- 后序遍历的原因，是因为涉及到前一位-1，会对单调递增特性有影响
- 为了方便挨个数字遍历，把int转换成string
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string str = to_string(n);
//转成字符串就是为了方便遍历
for(int i=str.size()-1;i>0;i--){
if(str[i-1]<=str[i]) continue;
//如果出现i-1>i，就把i换成9
else{
str[i]='9';
str[i-1]=str[i-1]-1;//ASCII码-1
}
}
return stoi(str);//string再转成Int
}
};
debug测试：逻辑错误
上面这段代码提交出现了逻辑错误，因为得到的并不是最大值。
修改版
本题贪心的策略，是遇到了相邻数字前一位>后一位，那么就让前一位变成前一位-1，但是此时后面的所有数字都需要变成9！
示例如下：
比如上面的例子，就必须考虑后面有多个小于前面的数字的情况。
- 修改版为了让小于情况下后面所有的数字都成为9，需要定义一个变量来控制9的起始位置
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string str = to_string(n);
//flag之后的元素都换成9，初值是不用换的情况
int flag=str.size();
//转成字符串就是为了方便遍历
for(int i=str.size()-1;i>0;i--){
if(str[i-1]<=str[i]) continue;
//如果出现i-1>i，就把i换成9
else{
flag=i;
str[i-1]=str[i-1]-1;//ASCII码-1
}
}
cout<<flag<<endl;
//遍历结束之后flag之后元素都是9
for(int i=flag;i<str.size();i++){
str[i]='9';
}
return stoi(str);//string再转成Int
}
};
- 时间复杂度：O(n)，n 为数字长度
- 空间复杂度：O(n)，需要一个字符串，转化为字符串操作更方便
debug测试
修改flag初始值后正确。
int转化为字符串的原因
因为本题需要对数字进行遍历，而我们没有直接的方式去获取和操作其特定位置的数字。因此，通常将整数转换为字符串以便于使用下标进行遍历和比较操作。在这种情况下，使用字符串会使操作更加简单直观。
to_string和stoi的用法
我们此处可以查阅c++string的文档：std::basic_string - cppreference.com
to_string() 是 C++ 标准库中的一个函数，它用于将各种数值类型（包括整数、浮点数等）转换为字符串。例如，to_string(123) 将返回字符串 "123"。
stoi() 函数则是 to_string() 的反向操作，用于将字符串转换为整数。例如**，stoi("123") 将返回整数 123**。值得注意的是，stoi() 函数会忽略字符串开头的空格，直到找到第一个非空格字符。如果这个字符是数字或者正负符号，函数会继续读取剩余部分，直到遇到非数字字符或到达字符串的末尾。
总结
本题只要想清楚个例，例如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89。就可以很自然想到对应的贪心解法了。
想到了贪心，还要考虑遍历顺序，只有从后向前遍历才能重复利用上次比较的结果。文章来源：https://www.toymoban.com/news/detail-530764.html
最后代码实现的时候，也需要一些技巧，例如用一个flag来标记从哪里开始赋值9。文章来源地址https://www.toymoban.com/news/detail-530764.html
到了这里，关于DAY40：贪心算法（九）单调递增的数字（贪心的思路）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
