单调递增的数字

题目详细：LeetCode.738

由题可知：

• 对于单调递增的数字，要保证其相邻的数字满足x <= y
• 假如数字不是单调递增的，那么要找出小于或等于 n 的最大数字，且数字是单调递增的

那么我们要解决的问题就是两个：

• 如何判断数字是不是单调递增的
• 如果数字不是单调递增的，那么如何确定小于或等于 n 的最大数字

对于解决第一个问题：

• 我们可以将数值转为字符串，再转为字符数组来遍历各个位上的数字，通过比较来判断相邻的数字是否单调递增
• 有两种遍历形式，从前往后遍历数字，或者从后往前遍历数字
• 如果从前往后遍历，那么高位的数字会优先被确定，假如低位的数字发生了非递增情况需要改变数值，那么则可能影响到高位数字的变化，由于高位数字已被确定，所以要修改估计很麻烦
• 所以这道题要选择从后往前遍历，从低位的数字开始确定，受到低位数字影响的高位数字也能在后续遍历过程中得到处理

对于解决第二个问题：

• 从后往前遍历数字，并比较低位和高位数字来判断是否递增
• 如果高位数字 > 低位数字，说明这两个相邻的数字是非递增的，所以低位数字要变大，为了满足递增需求所以至少要比高位数字大
  • 在这道题中，题目已要求找出小于或等于 n 的最大数字，所以为了满足最大数字的要求，我们直接将高位数字之后的低位数字都赋值 9 就行了
  • 低位数字如果变大，肯定是需要向高位借数的，所以高位数字也要相应的高位数字 - 1，最终结果才不会大于 n
• 如果相邻的数字是递增的，那么无需处理，继续往前遍历
• 这里定义了一个变量start， 来表示从哪一位开始对其后续位数都赋 9，使得结果是小于或等于 n 的最大数字。

Java解法（贪心）：

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));}
}

这道题我想到解法后，也知道可以将数字转数组后再进行操作，但是为了尽可能的降低空间复杂度，我打算直接对n来进行操作，从低位向高位逐位获取数字并进行比较，后续思路与上述解法思路相同；

但是绞尽脑汁之后还是放弃了，因为这样操作的话，标记start就显得有些复杂了，也没有简洁的逻辑思路将其后续位置的数字都变成9，只能是从头再遍历一次数字才能得知正确结果；

而且这种解法在操作n的过程中就已出错，所以发现我是小题大做了，还是得将数字转数组后再进行操作会好理解些。

监控二叉树

题目详细：LeetCode.968

这道题属实是直接把我CPU给烧了，不过看完题解之后很快就理解了，第一次发现原来还有状态标记和转移这种思路，详细的题解可以查阅：《代码随想录》— 监控二叉树

Java解法（贪心，后序遍历）：

class Solution {private int ans = 0;public int minCameraCover(TreeNode root) {// 最后对根节点的状态做检验，如果根节点是无被覆盖状态，那么需要在根节点放置一台摄像机。if(this.dfs(root) == 0){this.ans++;}return this.ans;}/*节点的状态值：0:表示无被覆盖 1:表示有摄像头2:表示有被覆盖后序遍历:根据当前节点的左右节点的状态，来判读当前节点的状态*/public int dfs(TreeNode root){if(null == root){// 空节点默认为有覆盖状态，避免在叶子节点上放摄像头return 2;}int left = this.dfs(root.left);int right = this.dfs(root.right);if(left == 2 && right == 2){// 如果左右节点都是被覆盖状态，那么当前节点的状态就应该是无覆盖，没有摄像头return 0;}else if(left == 0 || right == 0){// 如果左右节点都是无被覆盖状态，那当前节点此时应该放一个摄像头this.ans++;return 1;}// 如果左右节点至少存在1个摄像头，说明当前节点是被覆盖的return 2;}
}

总结