目录
452. 用最少数量的箭引爆气球
435. 无重叠区间
763.划分字母区间
今天的题目都算是 重叠区间 问题。
452. 用最少数量的箭引爆气球
为了让气球尽可能的重叠，需要对数组进行排序。
如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。
class Solution {public int findMinArrowShots(int[][] points) {
// Arrays.sort(points, (a, b) -> {
// if (a[0] == b[0]) {
// return Integer.compare(a[1], b[1]);
// }
// return Integer.compare(a[0], b[0]);
// });Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));int count = 1; // points 不为空至少需要一支箭for (int i = 1; i < points.length; i++) {if (points[i][0] > points[i - 1][1]) {count++;} else {points[i][1] = Math.min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界}}return count;}}- 时间复杂度：O(nlog n)，排序需要 O(NlogN) 的复杂度
- 空间复杂度：O( log n)，java所使用的内置函数用的是快速排序需要 logN 的空间
注意，排序这块需要用 Integer.compare(a[0], b[0])
因为一开始我用的是：
if (a[0] == b[0]) {return a[1] - b[1];
}
return a[0] - b[0];
当数组包含极大或极小的整数（如 Integer.MIN_VALUE 和 Integer.MAX_VALUE）时，直接使用减法计算差值可能导致 整数溢出，则会产生溢出错误。
为了避免溢出，可以使用 Integer.compare 方法代替减法，因为它可以安全地比较两个整数而不会产生溢出。Integer.compare(a[0], b[0])：会返回一个负值、零或正值，分别表示 a[0] 小于、等于或大于 b[0]。
435. 无重叠区间
按左边排序，不管右边顺序。相交的时候取最小的右边。
与452很类似，简单。
class Solution {public int eraseOverlapIntervals(int[][] intervals) {if (intervals.length == 1) {return 0;}Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));int count = 0;for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] < intervals[i-1][1]){intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);count++;}}return count;}
}763.划分字母区间
在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
可以分为如下两步：
- 统计每一个字符最后出现的位置（很妙，这个记录法，详见代码部分）
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
代码部分注意看下面那个简洁部分，注释的部分for循环中有点麻烦。但是思路逻辑什么的都是一样的。
class Solution {public List<Integer> partitionLabels(String s) {
// int[] str = new int[26];
// for (int i = 0; i < s.length(); i++) {
// str[s.charAt(i) - 'a'] = i; // 记录每个字符出现的最后一次的index
// }
// List<Integer> result = new LinkedList<>();
// for (int i = 0, start = 0, end = str[s.charAt(0)-'a']; i < s.length(); i++) {
// if (i == end){
// result.add(end-start+1);
// if (i == s.length()-1){
// break;
// }
// end = str[s.charAt(i+1)-'a'];
// start = i+1;
// }else {
// end = Math.max(end,str[s.charAt(i)-'a']);
// }
// }
// return result;//简洁版本int[] str = new int[27];for (int i = 0; i < s.length(); i++) {str[s.charAt(i) - 'a'] = i; // 记录每个字符出现的最后一次的index}List<Integer> result = new LinkedList<>();for (int i = 0, start = -1, end = 0; i < s.length(); i++) {end = Math.max(end,str[s.charAt(i)-'a']);if (i == end){result.add(end-start);start = i;}}return result;}}第三十天的总算是结束了，直冲Day31！
