目录

• 1. 用最少数量的箭引爆气球
• 2. 无重叠区间
• 3. 划分字母区间
• 4. 合并区间
• 5. 单调递增的数字
• 6. 买卖股票的最佳时机含手续费
• 7. 监控二叉树

1. 用最少数量的箭引爆气球

452. 用最少数量的箭引爆气球-中等

局部最优：当气球重叠时，一起射，所用弓箭最少。
对数组排序，如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。

var findMinArrowShots = function(points) {points.sort((a, b) => a[0] - b[0]);let ans = 1;for(let i = 1; i < points.length; i++) {if(points[i][0] > points[i - 1][1]) {ans++;}else{points[i][1] = Math.min(points[i][1], points[i - 1][1]);}}return ans;
};

总结：感觉这道题，虽然有了点思路，但不知道从何下手。发现代码其实很简洁，当points[i]与points[i - 1]无交集时，弓箭数直接加一，否则更新points[i]右端点的值。

2. 无重叠区间

435. 无重叠区间-中等

思路：知道这道题要排序，但不清楚具体应该怎么排序，排完序之后进行什么操作？

• 按照右边界排序，就要从左向右遍历，因为右边界越小越好，只要右边界越小，留给下一个区间的空间就越大，所以从左向右遍历，优先选右边界小的。
• 按照左边界排序，就要从右向左遍历，因为左边界数值越大越好（越靠右），这样就给前一个区间的空间就越大，所以可以从右向左遍历。

以下解法采用，按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
局部最优：按右边界排序后，优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优：选取最多的非交叉区间。

重点：直接求重叠区间，是很复杂的。把问题转换成求最大非重复区间个数，求个数时，用分割点做标记。

按右边界排序

var eraseOverlapIntervals = function(intervals) {// 按右边界排序intervals.sort((a, b) => a[1] - b[1]);let ans = 1;let end = intervals[0][1];for(let i = 1; i < intervals.length; i++) {if(intervals[i][0] >= end) {end = intervals[i][1];ans += 1;}}return intervals.length - ans;
};

按左边界排序

var eraseOverlapIntervals = function(intervals) {// 按照左边界升序排列intervals.sort((a, b) => a[0] - b[0])let count = 1let end = intervals[intervals.length - 1][0]// 倒序遍历，对单个区间来说，左边界越大越好，因为给前面区间的空间越大for(let i = intervals.length - 2; i >= 0; i--) {if(intervals[i][1] <= end) {count++end = intervals[i][0]}}// count 记录的是最大非重复区间的个数return intervals.length - count
}

3. 划分字母区间

763. 划分字母区间-中等

思路：

1. 统计每个字符最后出现的位置
2. 从前向后遍历字符串，更新字符的最远出现下标。如果找到字符最远出现位置下标与当前下标相等，就说明找到了分割点

var partitionLabels = function(s) {let hash = {};//  统计每个字符出现的最远位置for(let i = 0; i < s.length; i++) {hash[s[i]] = i;}let ans = [];let l = 0, r = 0;for(let i = 0; i < s.length; i++) {r = Math.max(r, hash[s[i]]);if(r === i) {ans.push(r - l + 1);l = i + 1;}}return ans;
};

4. 合并区间

56. 合并区间-中等

重点：新建一个数组，然后不断更新这个数组中区间段的右端点。

var merge = function(intervals) {// 按区间的左端点排序intervals.sort((a,b)=>a[0]-b[0]);const ans=[];for(let i=0;ilet l=intervals[i][0],r=intervals[i][1];//  区间段中的区间左端点大于ans中右端点if(ans.length==0||l>ans[ans.length-1][1]){ans.push([l,r]);}else{// 更新ans中右端点的值ans[ans.length-1][1]=Math.max(ans[ans.length-1][1],r);}}return ans;
};

5. 单调递增的数字

738. 单调递增的数字-中等

思路：遇到strNum[i - 1] > strNum[i]时，让strNum[i - 1]--，strNum[i]为9。

重点：要从后向前遍历，因为如果从前向后遍历，strNum[i - 1]--后可能会小于strNum[i - 2]。此外，还需要一个flag标记从哪里开始赋值为9的，然后需要把flag之后位的都赋值为9。

var monotoneIncreasingDigits = function(n) {n = n.toString();//  转成数组n = n.split('').map(item => {return +item;})let flag = Infinity;for(let i = n.length - 1; i > 0; i--) {if(n[i - 1] > n[i]) {flag = i;n[i - 1]--;}}for(let i = flag; i < n.length; i++) {n[i] = 9;}return n.join('');
};

6. 买卖股票的最佳时机含手续费

714. 买卖股票的最佳时机含手续费-中等
贪心

var maxProfit = function(prices, fee) {let ans = 0;let minPrice = prices[0];for(let i = 0; i < prices.length; i++) {if(prices[i] < minPrice) {minPrice = prices[i];}if(prices[i] >= minPrice && prices[i] <= minPrice + fee) continue;if(prices[i] > minPrice + fee) {ans += prices[i] - minPrice -fee;minPrice = prices[i] - fee;  // 买入和卖出只需要支付一次手续费}}return ans;
};

动态规划

7. 监控二叉树

968. 监控二叉树-困难

重点：从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

0：该节点无覆盖
1：本节点有摄像头
2：本节点有覆盖

var minCameraCover = function(root) {let ans = 0;function traversal(cur) {if(cur === null) return 2;let l = traversal(cur.left);let r = traversal(cur.right);if(l === 2 && r === 2) return 0;if(l === 0 || r === 0) {ans++;return 1;}if(l === 1 || r === 1) return 2;return -1;}if(traversal(root) === 0) ans++;return ans;
};