package Leetcode;

/**
 * @author zbl
 * @version 1.0
 * @content:
 * 给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例 1:

输入: N = 10
输出: 9
示例 2:

输入: N = 1234
输出: 1234
示例 3:

输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/monotone-increasing-digits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2020/12/15 12:25
 */
public class Solution738 {

    //方法一：
    public static int monotoneIncreasingDigits(int N) {
        String str=String.valueOf(N);
        int m=str.length();
        int index=0;
        char pre=str.charAt(0);
        int j=1;
        for(;j<m;j++){
            char c=str.charAt(j);
            if(c<pre){
                index=j-1;
                break;
            }
            pre=c;
        }
        if(j==m) return N;
        while(index>0 && str.charAt(index)==str.charAt(index-1)){
            index--;
        }
        StringBuilder sb=new StringBuilder();
        if(index==0 && str.charAt(index)=='1'){
            int i=0;
            while(i<m-1){
                sb.append(9);
                i++;
            }
        }else{
            for(int i=0;i<index;i++){
                sb.append(str.charAt(i));
            }
            int target=str.charAt(index)-'0';
            sb.append(target-1);
            int i=index+1;
            while(i<m){
                sb.append(9);
                i++;
            }
        }

        return Integer.valueOf(sb.toString());
    }

    //方法二：
    public  static int monotoneIncreasingDigits2(int N) {
        char[] chs=Integer.toString(N).toCharArray();
        int i=1;
        while(i<chs.length && chs[i-1] <= chs[i]){//找到第一个不符合要求的位置
            i+=1;
        }
        if(i < chs.length){
            while(i > 0 && chs[i-1] > chs[i]){//从不符合要求的前一个位置开始-1操作
                chs[i - 1] -= 1;
                i -= 1;
            }
            for(++i; i < chs.length; i++){
                chs[i]='9';
            }
        }
        return Integer.parseInt(new String(chs));
    }

    public static void main(String[] args) {
        System.out.println(monotoneIncreasingDigits2(10));
    }
}