738.单调递增的数字

思路： 从后向前遍历，如果前一个数比后一个数大，则前一个数-1，后面的数都变成9.
思路不难，但实现的代码还是有一点繁琐的。

以下是用List实现的代码。

class Solution {public int monotoneIncreasingDigits(int n) {List<Integer> list=new ArrayList<>();//定义数组存储while(n>0){list.add(n%10);n=n/10;}Collections.reverse(list);Integer[] nums=list.toArray(new Integer[list.size()]);for(int i=nums.length-1;i>0;i--){if(nums[i-1]>nums[i]){nums[i-1]=nums[i-1]-1;for(int j=i;j<nums.length;j++){nums[j]=9;}}}int res=0;for(int i=0;i<nums.length;i++){res=res*10+nums[i];}return res;}
}

还可以用String实现：

class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] chars = s.toCharArray();int start = s.length();for (int i = s.length() - 2; i >= 0; i--) {if (chars[i] > chars[i + 1]) {chars[i]--;start = i+1;}}for (int i = start; i < s.length(); i++) {chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
}

968.监控二叉树

一刷先不做了

贪心算法总结篇