代码随想录算法训练营第三十七天|738.单调递增的数字、968.监控二叉树、总结

代码随想录 (programmercarl.com)

738.单调递增的数字

一、暴力解法

从大大小遍历各个位，找到最先满足条件的单调递增数字

力扣上超时了

二、贪心思路

给定数字从后往前遍历，发现大于的情况，就将前一位-1，当前改为9

以下是错误?代码：

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        for (int i = chars.length - 1; i >= 1; i--){
            if (chars[i - 1] > chars[i]){
                chars[i - 1]--;
                chars[i] = '9' ;
            //字符9才是9，如果直接写9，就是'\t'
            }
        }
        return Integer.parseInt(String.valueOf(chars));
    }
}

?错误原因：100的时候输出的结果是90，因为0和0不满足大于关系，不会改变为9。

但其实，这里一旦前面有大于关系，后面所有位数都要改为9才可以，这时，就需要定义一个start，来记录从start开始直到末尾，所有都赋值为9。

正确?代码：

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

968.监控二叉树

卡尔：“本题是贪心和二叉树的一个结合，比较难，一刷大家就跳过吧。”

====所以暂时跳过了====

总结?

局部最优==》全局最优。

贪心无套路，忽难忽易。