今日任务：

1. LeetCode738 单调递增的数字
2. LeetCode968 监控二叉树
3. 贪心算法总结

资料来源：

1. 代码随想录 | LeetCode738 单调递增的数字
2. 代码随想录 | LeetCode968 监控二叉树
3. 代码随想录 | 贪心算法总结

1 LeetCode738 单调递增的数字

输入: n = 10
输出: 9

输入: n = 1234
输出: 1234

输入: n = 332
输出: 299

这题一开始看的时候的想法就是，这跟贪心有关系吗，不知道怎么贪。在看示例3的时候有了感觉，从后往前检查，如果有遇到不是单调的两个数字，比它小的最大的数字一定是较大的数位-1，较小的数位为9的。比如说332，从后往前检查的第一个就是2和3，如果要找比它小的而且是单调的，那么一定是2变成9，3变成2，这样整体就变成了329，再继续检查这个新的2和3，2 -> 9，3 -> 2，就得到了299。

另外，一旦有一个数位被置为9，那么比它小的所有数位都需要再置为9，以保证之前检查过的数位的单调性。比如说100，第一次检查0和0，是单调的；第二次检查1和0的时候就不是单调的了，这时需要将1 -> 0，0 -> 9，那么此时这个数字整体就是90，但是它不是单调数字，之前检查过的0失去了单调性，需要重新置为9。

python
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        n = str(n)
        n = list(n)
        n.reverse()
        n = list(map(int, n))
        
        pointer_9 = 0  # 列表已经反转 终点即是起点
        for i in range(len(n) - 1):
            if n[i] < n[i + 1]:
                pointer_9 = i
                n[i] = 9
                n[i + 1] -= 1

        for i in range(pointer_9):  # 按反转顺序来 置9
            n[i] = 9
            
        n.reverse()
        n = list(map(str, n))
        return int("".join(n))

2 LeetCode968 监控二叉树

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

这题的贪心很容易想到，那就是所有的叶子节点不能有摄像头，从叶子节点的父节点一级开始，竖方向上每隔两个节点设置一个摄像头，直到根节点。

首先，从上往下肯定是后序遍历没跑了；其次，因为给定的二叉树并没有限制对二叉树的读写，所以可以在遍历中使用。一个节点，它的状态可以是未覆盖、已被覆盖或者已设置摄像头三种情况。如果要实现思路，首先遍历中遇见叶子节点肯定是直接跳了；其次，如果左节点和右节点都是已覆盖区域，也可以直接跳过，由该节点的父节点来设置摄像头，这样就达成了“竖方向上每隔两个节点设置一个摄像头”；之后，如果左节点/右节点有未覆盖区域，那么为了保证所有区域都被覆盖，该节点必须设置一个摄像头；最后，如果左节点/右节点有摄像头，则设置该节点为已覆盖。注意后两个判断顺序不能变，防的就是一个节点的子节点一个有摄像头，一个是未覆盖，这时候必须给该节点上一个摄像头。

最后，因为检查都是对该节点的子节点进行检查，所以根节点并没有被检查过，所以最后必须给根节点单独检查是否是未覆盖，如果是就给根节点多加一个摄像头。（也可以给根节点多加一个虚拟的父节点，从虚拟父节点开始后序遍历来解决）

python
from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        if root.left is None and root.right is None:
            return 1
        monitor_number = 0
        stack = deque()
        stack.append(root)
        while len(stack) > 0:
            node = stack.pop()
            if node is None:
                node = stack.pop()
                # 规定0是未覆盖 1是有覆盖 2是有摄像头
                if node.left is None and node.right is None:
                    continue  # 叶子节点 不作处理
                if (node.left is not None and node.left.val == 1) and (node.right is not None and node.right.val == 1):
                    continue  # 左节点和右节点都是覆盖区域 不作处理
                if (node.left is not None and node.left.val == 0) or (node.right is not None and node.right.val == 0):
                    monitor_number += 1
                    node.val = 2
                    continue  # 左节点/右节点有未覆盖区域
                # 先检查子节点是否有未覆盖区域 再检查子节点有无摄像头 保证优先对未覆盖区域进行覆盖
                if (node.left is not None and node.left.val == 2) or (node.right is not None and node.right.val == 2):
                    node.val = 1
                    continue  # 左节点/右节点有摄像头 修改状态为有覆盖
            else:
                stack.append(node)
                stack.append(None)
                if node.right is not None:
                    stack.append(node.right)
                if node.left is not None:
                    stack.append(node.left)
        if root.val == 0:  # 因为遍历时都是对遍历节点的子节点进行检查 所以根节点并没有检查过是否被覆盖 在这里进行检查
            monitor_number += 1
        return monitor_number

3 贪心算法总结

贪心没有框架，没有显著的题目特征，就区间问题还算是比较典型的贪心题目，只能多做了，嫖个图在这。