package com.lxf.test;

public class MonotoneIncreasingDigits {
	public static void main(String[] args) {
		//1-9 1-9
		// 10  9
		// 22 22
		// 15 15
		// 76 69
		// 45 45
		//131 129
		//110 99
		//210 199
		//1101 999
		//3433 3399
		//3354 3349
		//332 299
		System.out.println(monotoneIncreasingDigits(10));
	}
   public static int monotoneIncreasingDigits(int N) {
		//获取正整数N最大的位数maxDigital
	   int maxDigital=1;
	   int m=N;
	   //获取当前位数字的基数(用于截取数字)
	   int base=1;
	   while(m/10!=0) {
		   maxDigital++;
		   m/=10;
		   base*=10;
	   }
	   //循环位数
	   int i=maxDigital;
	   //获取第一位上的数字
	   int first,second;
	   second=N/base;
	   while(i>1) {
	   		//从高位第一位开始往下搜索(第二次直接拿second就好)
		   first=second;
		   //从高位第二位开始往下搜索
		   if(i!=2) {
			   second=(N%base)/(base/10);
		   }else {
			   second=N%10;
		   }
		   //当前位数字大于下一位数字开始处理
		   if(first>second) {
		   	   //获取base2,当前前一位数的基数
			   int base2=base*10;
			   int j=i+1;
			   while(j<=maxDigital) {
			   	   //first的前一位
			   	   int zero=0;
			   	   //最高位上的数和其它位上的数计算方式不一样
				   if(j==maxDigital) {
					   zero=N/base2;
				   }else {
					   zero=N%(base2*10)/base2;
				   }
				   //如果zero为最高位，并且最高位和下一位相等直接返回结果就好
				   if(j==maxDigital&&zero==first) {
					   return (N/base2)*base2-1;
				   }
				   //如果first大于zero,说明first可减去1，first后的全置为9(最大)
				   if(first>zero) {
					   return N-N%(base2/10)-1;
				   }
				   first=zero;
				   j++;
				   base2*=10;
			   }
			   return (N/base)*base-1;
		   }
		   i--;
		   base/=10;
	   }
	   return N;
   }
}

2. 贪心法(官方题解，想法一样，实现不一样)

class Solution {
    public int monotoneIncreasingDigits(int N) {
        char[] strN = Integer.toString(N).toCharArray();
        int i = 1;
        //从高位向低位寻找高位数字大于高位下一位的数字
        while (i < strN.length && strN[i - 1] <= strN[i]) {
            i += 1;
        }
        //如果这个数字小于strN的长度就处理
        if (i < strN.length) {
        	//从这个位置开始减1，如果减完1大于等于这个位置前一位的数字就不必要继续
        	//否则这个位置的前一位持续减一
        	//比如332  第二位大于第三位,首先第二位减一等于2小于第一位，
        	//所以第一位还要减去1，等于222进入下一步处理
            while (i > 0 && strN[i - 1] > strN[i]) {
                strN[i - 1] -= 1;
                i -= 1;
            }
            //将最后一次减1的位数字后面所有数字都置为9
            //222->299
            //如果
            for (i += 1; i < strN.length; ++i) {
                strN[i] = '9';
            }
        }
        return Integer.parseInt(new String(strN));
    }
}