Leetcode 738 单调递增的数字

题意理解：

? ? ? ? 即给定一个整数N,要求返回一个小等于N的数。

? ? ? ? 且从左到右，数字成递增排列，即满足x1<=x2。

? ? ? ? 如：????????n = 332????????输出: 299

????????如：????????n = 1234? ? ? ? 输出: 1234

解题思路：

? ? ? ? 从两个角度考虑，从左到右确定这个目标数，还是从右到左确定这个目标数。

? ? ? ? 1.从左到右考虑，332，i=0,1时，符合递增，但i=2时，不符合递增，且取不到>=3的值

? ? ? ? 2.从右到左考虑，332，i=2时，取到2，2会限制前面取到很小的数字，将向下调整

? ? ? ? ? ? ? ? i=2时，取数字9，i=1，时做-1, 则有? ? ? ? 329，此时29满足条件。

? ? ? ? ? i=1时，取到数字2时，会限制前面取很小的数字，则将数字向下调整

? ? ? ? ? ? ? ? i=1时，取数字9，i=0，时做-1，则有????????299，此时299满足调整，切实最大的满足条件的值。

? ? ? ??

? ? ? ? 采用贪心思路解题，全局最优解：满足条件的最大值

? ? ? ? 局部最优解，为了使高位取到尽可能大的值，地位要给出能取到的最大值。

1.贪心解题

public int monotoneIncreasingDigits(int n) {
        char[] sNum=String.valueOf(n).toCharArray();
        //设置从哪个节点开始设置9
        int flag=sNum.length;
        for(int i=sNum.length-1;i>0;i--){
            if(sNum[i]<sNum[i-1]){
                flag=i;
                sNum[i-1]--;
            }
        }
        for(int i=flag;i<sNum.length;i++){
            sNum[i]='9';
        }
        return Integer.parseInt(String.valueOf(sNum));
    }

2.分析

时间复杂度：O(n) 遍历满足条件的数的时间

空间复杂度：O(n) 保存结果所需的空间。

n为输入数的位数。

先确定末尾数，再逐步确定前面的数。