*56. 合并区间

leetcode题目地址

重叠区间，若前一个区间的右边界大于等于当前区间的左边界，则有重叠，合并两个区间。

时间复杂度： $O(nlogn)$
空间复杂度： $O(logn)$

// java
class Solution {public int[][] merge(int[][] intervals) {if(intervals.length<=1) return intervals;Arrays.sort(intervals, (a, b) -> {if(a[0] == b[0]) return a[1] - b[1];return a[0]-b[0];});List<int[]> result = new LinkedList<>();result.add(new int[]{intervals[0][0], intervals[0][1]});for(int i=1; i<intervals.length; i++){if(intervals[i][0] <= result.getLast()[1]){int left = result.getLast()[0];int right = Math.max(intervals[i][1], result.getLast()[1]);  result.removeLast();result.add(new int[]{left, right});}else{result.add(intervals[i]);}}return result.toArray(new int[result.size()][]);}
}

*738. 单调递增的数字

leetcode题目地址

局部最优：当前一个数字大于当前数字时，将前一个数字减一，当前数字置为9。

确定遍历顺序：例如332，若从前向后遍历，i=1时，符合题目要求；当i=2时，前一个数字大于当前数字，将前一个数字减一，当前数字置为9，得到329，依旧不符合题意。

因此，需要从后向前遍历，每一步的操作是基于上一步大结果。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {// public boolean isValid()public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] arr = s.toCharArray();int flag = arr.length;for(int i=arr.length-1; i>0; i--){if(arr[i-1] > arr[i]){arr[i-1]--;flag = i;}}for(int i=flag; i<arr.length; i++){arr[i] = '9';}return Integer.parseInt(String.valueOf(arr));}
}

*968. 监控二叉树

leetcode题目地址

借助后序遍历查看当前结点是否需要加摄像头。
结点有三种状态：
0：当前结点无覆盖
1：当前结点有摄像头
2：当前结点有覆盖

尽可能少的安装摄像头，要在叶结点的上一层安装摄像头，然后向根节点方向没个两个节点加一个摄像头；当遇到空节点时，结点状态应该是有覆盖，这样就可以在叶结点的父节点上安摄像头了。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int cnt = 0;public int postOrder(TreeNode root){if(root == null) return 2;int left = postOrder(root.left);int right = postOrder(root.right);if(left == 0 || right == 0) {// 左右孩子结点有无覆盖 当前结点加摄像头cnt++;return 1;}if(left == 2 && right == 2) {// 左右节点均有覆盖 当前结点无覆盖 return 0;}if(left == 1 || right == 1){return 2;}return -1;}public int minCameraCover(TreeNode root) {int flag = postOrder(root);if(flag == 0) cnt++;return cnt;}
}