力扣128. 最长连续序列 || 452. 用最少数量的箭引爆气球

最长连续列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

输入：nums = [1,0,1,2]
输出：3

首先这道题，第一眼看到就觉得应该使用Set来解决。为什么呢？首先第一个需要使用set来去重，第二个set可以根据从contains来查找元素。

OK，那我们就先把元素存到set里

Set<Integer> set = new HashSet<>();
for(Integer num : nums){
	set.add(num);
}

之后呢？题目说复杂度O(n)，所以呢排序不行，那只能另辟蹊径了。

题目要求找出最大的连续长度，那么我们是不是要想办法找到他的起点。但是呢又有一个问题，如果不同元素直接差值很大呢，比如400 301 302 -500。这样不管是说我们先找到最小元素然后去逐步+1，还是第一个元素来计算都很耗时。

那怎么办呢？我们可以采用直接计算的方法。

起点 x 必然满足 x-1 不在集合中，所以遍历集合中的每个元素 x，仅当 x 是起点时（!set.contains(x-1)），才尝试扩展序列。

这个起点是一个临时起点，并不是说他一定是整个集合的起点。比如400 300 301。400-1必然是找不到，但不能说400是整体的起点

从起点 x 开始，依次检查 x+1, x+2, … 是否存在于集合，直到无法继续。序列长度就为y - x。保存每次查找的结果，最后使用最长的链路

for(x : set){
	//如果还能找到更小的，那就先不使用，去set里找下一个元素
	if(set.contains(x-1){
		continue;
	}
	//如果当前这个数x，找不到x-1的了，那就先用x来查
	int y = x + 1;
	//如果有x+1的数，那就用y记录下来
	while(set.contains(y)){
		y++;
	}
	//一次次的循环， 直到找到最大的y-x
    ans = Math.max(ans,y-x);
}

题解：

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for(Integer num : nums){
            set.add(num);
        }

        int ans = 0;
        //假设set里是5 4 3 2 1 0
        for(Integer x : set){
            //如果还能找到更小的，那就直接退出
            if(set.contains(x - 1)){
                continue;
            }
            //如果当前这个数x，找不到x-1的了，那就先用x来查
            int y = x + 1;
            //如果有x+1的数，那就用y记录下来
            while(set.contains(y)){
                y++;
            }
            //一次次的循环， 知道找到最大的y-x
            ans = Math.max(ans,y-x);
        }
        return ans;

    }
}

用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

‍输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

‍输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

首先看到这题，我最初想的是不断计算两个节点之间是否覆盖，太过于复杂

后来看到题解后才想到可以用排序的方法来计算是否覆盖

按右端点进行排序后，每次在右端点处射箭，就可以覆盖掉所有左端点<=当前右端点的气球。射在右端点能最大化的覆盖重叠的气球。

若当前气球的左端>上支箭矢的位置（上一个范围的右端点），表明需要新加一支箭，并更新当前箭的位置为当前气球的右端点。
否则则表明，当前气球被覆盖，无需处理

首先我们对所有的坐标进行排序（以end坐标为值计算）

Arrays.sort(points,(a,b) -> Integer.compare(a[1],b[1]));

接下来只需要判断，下一个坐标的左侧，是否大于我们这个坐标的右侧即可判断出是否覆盖。如果不覆盖则箭数+1

‍int end = points[0][1];  //先定义出初始的end坐标，排序后的第一个元素的右侧。

for(int i = 1; i < points.length; i++){
	if(points[i][0] > end){  //当前元素的左侧，大于end的右侧
		arrows++;
		end = points[i][1]; 
	}
	//注意，如果当前元素在我们end的范围内，end也不需要更新。因为如果更新，那么我们第一个节点就会无法覆盖到。
}

解：

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,(a,b) -> Integer.compare(a[1],b[1]));
        int arrows = 1;
        int end = points[0][1];
        for(int i = 1; i < points.length; i++){
            if(points[i][0] > end){
                arrows++;
                end = points[i][1]; 
            }
        }
        return arrows;
    }
}