算法37|738，714，968

738.单调递增的数字

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        #将数字变成列表
        ls = [i for i in str(n)]
        #范围是到1，因为他还会判断i-1
        for i in range(len(ls)-1,0,-1):
            if int(ls[i-1]) > int(ls[i]):
                ls[i-1] = str(int(ls[i-1])-1)
                ls[i:] = '9'*(len(ls)-i)
        result = int("".join(ls))
        return result

https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html

局部最优：永远都9，前面永远都减1

全局最优：这样就是最大的。

遍历这个数字，前面如果比后面大，前面的减一，后面的变成9

二刷（未ac）

var monotoneIncreasingDigits = function(n) {
    let digits = Array.from(String(n),Number)
    let flag = Infinity
    for(let i = digits.length-1;i>0;i--){
        if(digits[i-1]>digits[i]){
            flag = i
            digits[i-1] = digits[i-1]-1
            digits[i] = 9
        }
    }
    for(let i = flag;i<digits.length;i++){
        digits[i] = 9
    }
    let result = digits.join("")
    return +result
    
};

714. 买卖股票的最佳时机含手续费 （可以跳过）

贪心解法可以跳过，有点难以理解，即使理解了，后面也会忘，还是在动态规划章节在好好做本题。

https://programmercarl.com/0714.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA%E5%90%AB%E6%89%8B%E7%BB%AD%E8%B4%B9.html

968.监控二叉树 （可以跳过）

var minCameraCover = function(root) {
    // 使用后序遍历，因为我们需要从叶子节点开始。因为下面的节点没有放的话，所少的摄像头比上面的多。所以需要使用后序遍历
    // 节点有三个状态：0 未覆盖（没有摄像头，没有监控到） 1 放摄像头 2 覆盖
    const traversal = function(node){
        // 左右中
        // 终止条件
        // 因为我们需要保证叶子节点的父节点也需要放上摄像头，如果别的状态，那么叶子节点需要一个摄像头
        if(node === null){
            return 2
        }
        // 左
        let left = traversal(node.left)
        // 右
        let right = traversal(node.right)
        // 处理逻辑
        // 情况1：左右节点都有覆盖
        if(left === 2 && right === 2){
            return 0
        }
        // 情况2：左右节点至少有一个无覆盖
        // if(left === 0 && right === 0){
 
        // }if(left === 0 && right === 1){
 
        // }if(left === 0 && right === 2){
 
        // }if(left === 1 && right === 0){
 
        // }if(left === 2 && right === 0){
 
        // }
        if(left === 0 || right ===0){
            result ++ 
            return 1
        }
        // 情况3：左右节点至少有一个摄像头
        if(left === 1||right ===1){
            return 2
        }
        return -1
    }
    let result = 0
    if(traversal(root) === 0){
        result ++
    }
    return result
    
};

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

https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html

总结

看完了，很困

可以看看贪心算法的总结，贪心本来就没啥规律，能写出个总结篇真的不容易了。

https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E7%AF%87.html