Leetcode 435. 无重叠区间(Java实现 超详细注释!)

Leetcode 435. 无重叠区间

动态规划,这道题动态规划的细节有点难理解,也很难想清楚,加了详细的注释,方便日后复习,也希望能帮到其他小伙伴,如有错误,欢迎指正!

Java实现:

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 判空,没有区间当然是不需要移除啦
        if (intervals.length == 0) return 0;
        // 我们首先按照每个区间的左值排序,在这里我们其实不需要考虑左值相等,右边不一样怎么排序的情况;
        // 由于我们不需要知道具体去除哪一个区间,只需要知道去除的数量,因此我们后面的动态规划会自动找到最优的情况
        Arrays.sort(intervals,new Comparator<int []>(){
            public int compare(int[] arr1,int[] arr2){
                return arr1[0] - arr2[0];
            }
        });
        // 动态规划数组大小只需要等于区间的个数即可
        int n = intervals.length;
        // 初始化动态规划数组
        int[] dp = new int[n];
        // 至少都可以留一个区间,所以无论如何都会大于1,我们先都赋值1即可
        Arrays.fill(dp,1);
        // 动态规划开始,这里有点精妙,其实就是模拟流程
        // 其实外层循环就是完整遍历每一个区间
        for (int i = 0; i < n; i++){
            // 动态规划的流程如下:
            /**对应外层的每一个区间,我们都用这个区间和该区间左边的比较,为什么比左边?
            因为我们是排序过的,右边的区间左值只要大于左边区间的右值,那么这两个区间是可以同时保留的;
            而前一个区间可以可以和再前面的区间同时保留,因此到这个区间为止我们就最多能保留dp[j] + 1即可
            到这里好像就结束了,其实没有,因为内层循环时,可能有多个区间,我们不知道匹配前面的哪个区间是最优的
            所以我们这里需要看dp[j] + 1和内循环的前一次的值(上一次存下来的dp[i])哪个大,哪个大我们就存哪个*/
            for (int j = 0; j < i; j++) {
                if (intervals[i][0] >= intervals[j][1]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
        }
        // num为可以保留的最大区间数
        // Arrays.stream().max()是java8新特性,因为数组不好进行最大值的获取,我们转成流并取出最大值,再将取出的最大值转为Int
        int num = Arrays.stream(dp).max().getAsInt();
        // 返回移除区间的最小数量
        return n - num;
    }
}
上一篇:*435. 无重叠区间(贪心)


下一篇:435. 无重叠区间