AlgoPressAppearance
0738-单调递增的数字
https://leetcode.cn/problems/monotone-increasing-digits
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。 给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 10
输出: 9
示例 2:
输入: n = 1234
输出: 1234
示例 3:
输入: n = 332
输出: 299
提示:
- 0 <= n <= 10^9
思路：有问题
考虑 ：1 位数，就等于他自己 考虑 : 2 位数，原来就是递增的就是他自己，如果是递减的，就是前一个数减1，后一个数变成9 考虑 : 3 位数，两位数-1，然后最后加9
从后往前计算有问题，比如 328 会求出 298 而不是 299
需要从前往后计算，如何知道第一位的数字？
参考代码
csharp
public class Solution {
public int MonotoneIncreasingDigits(int n) {
if(n == 0){
return 0;
}
int lastDigit = n % 10;
int lastSecondDigit = n / 10 % 10;
int result;
if(lastDigit >= lastDigit){
result = MonotoneIncreasingDigits(n / 10) * 10 + lastDigit;
}
else{
result = MonotoneIncreasingDigits( n / 10 - 1) * 10 + 9;
}
return result;
}
}
思路2：从前往后贪心计算
要尽可能的大，那么这个数从高位开始要尽可能地保持不变。那么我们找到从高到低第一个满足 str[i] > str[i+1] 的位置，然后把 str[i] - 1，再把后面的位置都变成 99 即可。对应可看下面的例子。
参考代码：转字符串
csharp
public class Solution{
public int MonotoneIncreasingDigits(int n){
char[] arr = n.ToString().ToCharArray();
int i=1;
//找出非递增的位置
while(i < arr.Length){
if(arr[i-1] <= arr[i]){
i++;
}
else{
break;
}
}
//开始扣减前一位
if(i<arr.Length){
while(i>0 && arr[i-1] > arr[i]){
arr[i-1]--;
i--;
}
for(int index = i+1; index < arr.Length; index++){
arr[index] = '9';
}
}
return Convert.ToInt32(new string(arr));
}
}
思路3：贪心优化查找 【巧妙】
在上一个思路中，当发现下一个数小于上一个数字的时候，我们把上个数字的数值-1，此时需要多考虑当-1之后，是否比以前小的情况。 这种情况，只有前两个数相同的时候才会发生，比如 33, 变成 32 ， 所以我们找到一个确切递增的max值，我们记录下来的索引就是需要更新的记录。
因为他比前面的数至少大于1 https://leetcode.cn/problems/monotone-increasing-digits/solution/jian-dan-tan-xin-shou-ba-shou-jiao-xue-k-a0mp/
csharp
public class Solution{
public int MonotoneIncreasingDigits(int n){
char[] arr = n.ToString().ToCharArray();
int max = -1;
int index = -1;
for(int i=0; i<arr.Length; i++){
if(arr[i] > max){
max = arr[i];
index = i;
}
if(i>0 && arr[i] < arr[i-1]){
arr[index]--;
//更新后面的9
for(int j=index+1;j<arr.Length;j++){
arr[j] = '9';
}
break;
}
}
return Convert.ToInt32(new string(arr));
}
}
复习 20220513
csharp
public class Solution {
public int MonotoneIncreasingDigits(int n) {
char[] arr = n.ToString().ToCharArray();
int max = -1;
int index = -1;
for(int i=0; i<arr.Length; i++){
if(arr[i] > max){ //从前往后找到最大的数
max = arr[i];
index = i;
}
//判断后面是否开始递减了
if(i>0 && arr[i] < arr[i-1]){
arr[index]--;
for(int j=index+1; j<arr.Length;j++){
arr[j] = '9';
}
break; //退出循环
}
}
//输出
int result = 0;
for(int i=0; i<arr.Length; i++){
result = result * 10 + (arr[i] - '0');
}
return result;
}
}
复习:20220320
注意要找到两个数，一个是严格递增的数，从这个数开始扣减1. 另外一个数是开始递减的数。 如果发现了这个数，说明需要开始处理。
如果每个数字都不相同，那么问题就简化为，找到递减的数，他前面的数字扣减1，后面都变成9就可以了， 比如 12321 就变成12299
但时当前面数字有相等的时候，比如 123321 此时我们不能直接扣减第二个3，这样结果就是 123299 出现递减了，所以我们要找到相等的第一个数。
所以从开始，我们可以记录严格递增的那个数，就是开始需要扣减的那个数，比如 123321 一直到第一个3都是严格递增的，所以记录 left = 2
然后我们记录后面是否有递减(nums[i] < nums[i-1])，是的话，就从 left 开始扣减
从严格递增的数字开始，扣减1，然后后面都变成99
csharp
public class Solution {
public int MonotoneIncreasingDigits(int n) {
int left = 0;
char[] strs = n.ToString().ToArray();
for(int i=1; i<strs.Length; i++){
if(strs[i] > strs[left]){ //找到严格递增的位置
left = i;
}
else if(strs[i] < strs[i-1]){ //如果发现有递减，说明需要处理，从严格递增的位置开始扣减
strs[left]--;
for(int j=left+1; j<strs.Length; j++){
strs[j] = '9';
}
break;
}
}
string s= new string(strs);
return Convert.ToInt32(s);
}
}