区间专题
贪心法的题都不容易啊，还是要多练
452. 用最少数量的箭引爆气球
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
示例 1： 输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2 解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
示例 2： 输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4
示例 3： 输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2
示例 4： 输入：points = [[1,2]] 输出：1
示例 5： 输入：points = [[2,3],[2,3]] 输出：1
提示：
- 0 <= points.length <= 10^4
- points[i].length == 2
- -2^31 <= xstart < xend <= 2^31 - 1
思路
排序+贪心
解法一：按左边界排序
public int findMinArrowShots(int[][] points) {
if (points.length == 0) return 0;
Arrays.sort(points, (o1, o2) -> Integer.compare(o1[0], o2[0]));
int count = 1;
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],points[i - 1][1]);//更新边界范围，取最小的边界，因为要满足两个区间的交集
}
}
return count;
}
解法二：按右边界排序
public int findMinArrowShots(int[][] points) {
if (points.length == 0) return 0;
Arrays.sort(points, (o1, o2) -> Integer.compare(o1[1], o2[1]));
int count = 1;
int rightValue = points[0][1];
for (int[] point : points) {
if(point[0] > rightValue){//出现断层
count++;//箭++
rightValue = point[1];//更新有边界
}
}
return count;
}
}
435. 无重叠区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2: 输入: [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3: 输入: [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
#思路
要理解本题哪里用到贪心了，贪心的思路就是由局部最优到整体最优，本题还需要一丢丢的逆向思维，求需要移除几个区间是集合无重复区间，可以反过来求有几个无重复的区间。
这题需要对集合的右边界小到大排序，左边界的排序无关紧要，排序后局部最优就是找到首个最小右边界，然后更新下一个无重复最小有边界，然后再更新下一个，重复此步骤，直到最后一个
- 局部最优：无重复最小右边界
- 整体最优：所有的无重复最小右边界
public int eraseOverlapIntervals(int[][] intervals){
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals,(a,b)->{
return Integer.compare(a[1],b[1]);
});
int right = intervals[0][1];//取排序后的第一个区间的有边界作为首个局部最优
int noRepCount = 1;
for (int i = 1; i < intervals.length; i++) {
if(intervals[i][0] >= right){
//等于 就是相邻 ，之前没注意，要仔细审题
noRepCount ++;
//更新下一个局部最优
right = intervals[i][1];
}
}
return intervals.length - noRepCount;
}
问题
在没有看题解之前，我都遇上了那些问题
- 首先有模糊的感觉，知道区间类的问题要排序，但是不知道怎么排序，脑袋里头没有想法
- 贪心的精髓还是没有掌握，如何由局部到整体
763.划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例： 输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
提示：
- S的长度在[1, 500]之间。
- S只包含小写字母 'a' 到 'z' 。
#思路
如何贪心：
可以分为如下两步：
- 统计每一个字符最后出现的位置
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
如图：
明白原理之后，代码并不复杂，如下：
public List<Integer> partitionLabels(String s) {
//同样的字母尽可能多的在一个片段中
int[] hash = new int[27];
for (int i = 0; i < s.length(); i++) {
hash[s.charAt(i) - 'a'] = i;//更新每个字母的最远边界
}
int left = 0,right = 0;
List<Integer> ans = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
//更新右边界
right = Math.max(right,hash[s.charAt(i) - 'a']);
if(i == right){
ans.add(right - left + 1);
left = i + 1;
}
}
return ans ;
}
56. 合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1: 输入: intervals = [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2: 输入: intervals = [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。 注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
提示：
- intervals[i][0] <= intervals[i][1]
#思路
一样是排序，但是此题要按照左去边界从小到大排序
分两种情况
- 要合并： 当前区间的左边界小于前一区间的右边界
- 不要合并：else
public int[][] merge(int[][] intervals) {
if(intervals.length == 1) return intervals;
Arrays.sort(intervals,(a,b)->{
return Integer.compare(a[0],b[0]);
});
List<int[]> res = new LinkedList<>();
int start = intervals[0][0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] > intervals[i - 1][1]) {
res.add(new int[]{start, intervals[i - 1][1]});
start = intervals[i][0];
} else {
intervals[i][1] = Math.max(intervals[i][1], intervals[i - 1][1]);
}
}
res.add(new int[]{start, intervals[intervals.length - 1][1]});
return res.toArray(new int[res.size()][]);
}
