单调递增的数字-贪心

package Leetcode;
/**
 * 给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
 */
/**
 * 注意到如果减小 str[i]str[i] 以后不满足 str[i-1] <= str[i]str[i−1]<=str[i]，那么肯定有 str[i-1] == str[i]str[i−1]==str[i]，此时就需要再 str[i-1] - 1str[i−1]−1，递归地会处理到某个位置 idxidx，我们发现 str[idx] == str[idx + 1] == ... = str[i]str[idx]==str[idx+1]==...=str[i] 。然后只要str[idx] - 1str[idx]−1，然后后面都补上 99 即可。
所以代码写起来很简单了。遍历各位数字的时候，求当前最大的数字 max。然后只在 max < arr[i]max<arr[i] 的时候才更新 max 对应的 idx（写法类似于查找数组中最大的元素，返回最小的下标）。接着判断是否有 arr[i] > arr[i + 1]arr[i]>arr[i+1]，如果是，那么 idx 位置数字减 11，后面的位置全部置 99 即可。
 */
public class dizengshuzi {
    public static void main(String[] args) {
        int N=332;
        System.out.println(monotoneIncreasingDigits(N));     
    }
    public static int monotoneIncreasingDigits(int N) {
        char []c=Integer.toString(N).toCharArray();
        int i=1;
        while(i<c.length&&c[i-1]<=c[i]){
            i+=1;
        }
        if(i<c.length){
            while(i>0&&c[i-1]>c[i]){
                c[i-1]-=1;
                i=i-1;
            }
            for(i+=1;i<c.length;i++){
                c[i]='9';
            }
        }
        return Integer.parseInt(new String(c));
    }
    
}