羊羊刷题笔记Day36/60 | 第八章 贪心算法P5 | 435. 无重叠区间、763. 划分字母区间、56. 合并区间

435 无重叠区间

今天的三题都是类似昨天452 用最少数量的箭引爆气球，重叠区间思想~ 区别就是判断区间重叠后的逻辑

思路

看到这道题目都冥冥之中感觉要排序
这里按照左边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
此时问题就是要求非交叉区间的最大个数。
这里记录非交叉区间的个数还是有技巧的，以 [ [1,2], [2,3], [3,4], [1,3] ] 为例子，排序后如图：

当确定区间 1 和 区间2 重叠后，如何确定是否与 区间3 也重贴呢？
✅就是取 区间1 和 区间2 右边界的最小值，因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分，并把这个最小值赋给第i个数组以便下一层遍历。（其实也可以int一个end来记录，但根据循环特性这样做提高空间效率）
如果这个最小值也触达到区间3，那么说明 区间 1，2，3都是重合的。
以此一个一个遍历判断下去，
整体代码如下：

public int eraseOverlapIntervals(int[][] intervals) {
    // 按左边界进行排序
    Arrays.sort(intervals,(a,b) -> {
        return a[0] - b[0];
    });

    // 初始化变量
    int count = 0;
    // 遍历数组
    for (int i = 1; i < intervals.length; i  ) {
        // 有重叠 - 上一个右边界大于当前左边界
        if (intervals[i - 1][1] > intervals[i][0]){
            // 需要删
            count  ;
            // 更新当前右边界 便于下一层循环
            intervals[i][1] = Math.min(intervals[i][1],intervals[i - 1][1]);
        }
    }
    return count;
}

• 时间复杂度：O(nlog n) ，有一个快排
• 空间复杂度：O(n)，有一个快排，最差情况(倒序)时，需要n次递归调用。因此确实需要O(n)的栈空间

763 划分字母区间

不太像贪心算法的题，但也体现了重叠区间思想

思路

（一想到分割字符串就想到了回溯hhh，但本题其实不用回溯去暴力搜索。这很直观体现回溯暴力效率低）
题目要求同一字母最多出现在一个片段中，那么如何把同一个字母的都圈在同一个区间里呢？
在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
可以分为如下两步：

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

思路：第一个遍历元素a，要想达到同一字母只出现在一个组合的目的，不得不遍历到下标8。而遍历到下标8，就不得不让其中元素都遍历到最后的元素，以达到同一字母只出现在一个组合的目的。因此以此循环，不断更新右边界。
如图：

明白原理之后，代码并不复杂，如下：

public List<Integer> partitionLabels(String s) {
    int[] arr = new int[26];
	// 转换成数组效率更高
	char[] s1 = s.toCharArray();
	for (int i = 0; i < s1.length; i  ) {
	    arr[s1[i] - 'a'] = i;
	}
	
	int right = 0,left = 0;
	List<Integer> list = new ArrayList<>();
	for (int i = 0; i < s1.length; i  ) {
	    right = Math.max(right,arr[s1[i] - 'a']);
	    if (i == right){
	        list.add(right - left   1);
	        left = right   1;
	    }
	}
	
	return list;
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)，使用的hash数组是固定大小

总结

这道题目leetcode标记为贪心算法，但说实话，没有感受到贪心，找不出局部最优推出全局最优的过程。就是用最远出现距离模拟了圈字符的行为。
但这道题目的思路类似于之前的452 用最少数量的箭引爆气球，所以有必要介绍做一做，感受一下

56 合并区间

重叠区间思想经典再现，有了之前几题基础会好做一些~

思路

本题的本质其实还是判断重叠区间问题。

今天的三题都是这个判断重叠区间 ，与452 用最少数量的箭引爆气球思想类似。

区别就是判断区间重叠后的逻辑，本题是判断区间重贴后要进行区间合并。

所以一样的套路，先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。

按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）

这么说有点抽象，看图：（注意看黑色箭头） 图中区间都是按照左边界排序之后了

知道如何判断重复之后，剩下的就是合并了，如何去模拟合并区间呢？

其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。这样省去很多复杂的逻辑代码

整体代码如下：

public int[][] merge(int[][] intervals) {
    // 按左边界排序
    Arrays.sort(intervals,(a,b)->{
        return a[0] - b[0];
    });

    // 涉及取最后一个元素 用LinkedList
    LinkedList<int[]> arr = new LinkedList<>();
    arr.add(intervals[0]);

    // 遍历数组
    for (int i = 1; i < intervals.length; i  ) {
        // 跟上一个元素相比 - 有重叠
        if (intervals[i][0] <= arr.getLast()[1]){
            // 更新最后一个元素右边界
            int start = arr.getLast()[0];
            int end = Math.max(arr.getLast()[1],intervals[i][1]);
            // 重新赋值
            arr.removeLast();
            arr.add(new int[]{start,end});
        }
        else // 没有重叠
            arr.add(intervals[i]);
    }

    return arr.toArray(new int[arr.size()][]);
}

• 时间复杂度: O(nlogn)
• 空间复杂度: O(logn)，排序需要的空间开销

学习资料：

435. 无重叠区间

763. 划分字母区间

56. 合并区间

这篇好文章是转载于：学新通技术网