738.单调递增的数字

题目链接：738. 单调递增的数字 - 力扣（LeetCode）

思路

将数字转换成字符数组形式，然后从后向前遍历，当遇到当前这个数大于后一个数的时候，这个数减一，他的后一个数赋为9，这也是贪心策略。

在代码实现上，可以设置一个start变量来记录需要变为 9 的起始位置。

代码

 1 版本1
 2 class Solution {
 3     public int monotoneIncreasingDigits(int N) {
 4         String[] strings = (N + "").split("");
 5         int start = strings.length;
 6         for (int i = strings.length - 1; i > 0; i--) {
 7             if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {
 8                 strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
 9                 start = i;
10             }
11         }
12         for (int i = start; i < strings.length; i++) {
13             strings[i] = "9";
14         }
15         return Integer.parseInt(String.join("",strings));
16     }
17 }

 1 版本2
 2 class Solution {
 3     public int monotoneIncreasingDigits(int n) {
 4         String s = String.valueOf(n);
 5         char[] chars = s.toCharArray();
 6         int start = s.length();
 7         for (int i = s.length() - 2; i >= 0; i--) {
 8             if (chars[i] > chars[i + 1]) {
 9                 chars[i]--;
10                 start = i+1;
11             }
12         }
13         for (int i = start; i < s.length(); i++) {
14             chars[i] = '9';
15         }
16         return Integer.parseInt(String.valueOf(chars));
17     }
18 }

968.监控二叉树

先欠着，二刷的时候在补上。。。

贪心总结

直接看卡哥的总结吧，链接：代码随想录 (programmercarl.com)