当前位置：首页 > article >正文

LeetCode hot 100 每日一题(10)——56. 合并区间

article 2025/3/18 16:10:33

这是一道难度为中等的题目，我们来看看题目描述：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 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] 可被视为重叠区间。

提示：

1 <= intervals.length <= $10^4$
intervals[i].length == 2
0 <= $start_i$ <= endi <= $10^4$

说人话解释：

求重叠的区间并集，然后返回所有的并集

题解

class Solution {

    public int[][] merge(int[][] intervals) {

        // 创建LinkedList存储合并后的空间，方便在尾部插入和删除元素

        LinkedList<int[]> res = new LinkedList<>();

        // 按照区间的起点进行排序

        Arrays.sort(intervals, (a, b) -> {return a[0] - b[0];});

        //先将第一个区间加入结果列表

        res.add(intervals[0]);

        //遍历剩下的所有区间，所以从i = 1开始

        for(int i = 1; i < intervals.length; i++){
  
            int[] curr = intervals[i]; // 当前遍历的区间，是列表

            int[] last = res.getLast(); // 获取结果列表中的最后一个区间


            // 如果当前区间起点小于或等于上一个区间的终点，说明区间有重叠

            if(curr[0] <= last[1]){

                // 更新结果列表中的最后一个区间的终点

                last[1] = Math.max(last[1], curr[1]);

            }else{

                // 如果没有重叠，直接将当前区间加入列表

                res.add(curr);

            }

        }

        //将LinkedList转换为二维数组返回

        return res.toArray(new int[1][1]);

    }

}

问题与解答

[NOTE] 问题1
Arrays.sort(intervals, (a, b) -> {return a[0] - b[0];});中(a, b) -> {return a[0] - b[0];}这是什么用法？
解答：
(a, b) -> {return a[0] - b[0];} 是 Lambda 表达式，用于 Java 8 及以上版本的简洁写法，相当于实现 Comparator<int[]> 接口的 compare 方法。
其作用是按照数组 intervals 的第一个元素（即起点 start_i）进行升序排序。
等价于：
Arrays.sort(intervals, new Comparator<int[]>() {
   @Override
   public int compare(int[] a, int[] b) {
       return a[0] - b[0];
   }
});
a[0] - b[0] 返回负数（a[0] < b[0]），则 a 排在 b 前面；
a[0] - b[0] 返回正数（a[0] > b[0]），则 b 排在 a 前面；
a[0] - b[0] 返回 0，则 a 和 b 位置不变（即视为相等）。

[NOTE] 问题2
int[] curr = intervals[i]; // 当前遍历的区间，是列表
int[] last = res.getLast(); // 获取结果列表中的最后一个区间
这里取出来的是列表还是数组？形如[i， j]的是列表还是数组？
curr[0]是当前区间的起点，curr[1]是当前区间的终点吗？
last[0]是结果列表中最后一个区间的起点，last[1]是结果列表中最后一个区间的终点吗？
解答：
取出的是数组，不是列表。这里 curr 和 last 都是 int[] 类型的数组，表示一个区间 [start, end]。形如 [i, j] 的数据结构是 int[] 数组，而不是 List Java 里没有像 Python 那样的列表（list），int[] 是固定大小的数组，而 List<int[]> 则是存储多个 int[] 的动态集合。
在 Java 中，数组（Array）和列表（List，通常指 ArrayList）是两种常见的数据结构

数组（Array）：大小是固定的，创建后不能更改长度。可以存储基本数据类型（如 int、double）也可以存储对象类型。
列表（List）：大小是动态的，可以根据需求增删元素。只能存储对象类型（ArrayList<int> 不合法，必须使用 ArrayList<Integer>）。

curr[0] 和 curr[1] 代表当前区间的起点和终点。
last[0] 和 last[1] 代表 res 结果列表中最后一个区间的起点和终点

[NOTE] 问题3
res.toArray(new int[1][1]);中的toArray用法是什么？
解答：

res.toArray(new int[0][0]) 用于将 LinkedList<int[]> res 转换为 二维数组 int[][]。

toArray() 方法作用：

toArray(new int[0][0]) 方式可以将 LinkedList<int[]> 直接转换为 int[][] 数组。
由于 res 是 LinkedList<int[]>，需要转换为 int[][] 返回，因此 toArray() 适用于数组转换。

等价于：
int[][] result = new int[res.size()][2];
for (int i = 0; i < res.size(); i++) {
   result[i] = res.get(i);
}
return result;
为什么用 new int[0][0]？

由于 toArray(T[] a) 需要传入一个 相同类型的数组，但不需要指定大小（JVM 会自动调整大小）。
new int[0][0] 只是一个占位符，toArray 会创建合适大小的 int[][] 并返回。

[NOTE] 问题4
LinkedList<int[]> res = new LinkedList<>();创建的是什么数据结构？是双链表LinkedList吗？
解答：
是 双向链表 LinkedList，LinkedList<int[]> 代表一个存储 int[] 数组的双向链表。

LinkedList<int[]> res = new LinkedList<>();
LinkedList<> 是 Java 的 双向链表实现，允许快速插入和删除元素。
这里 res 存储的是 int[] 类型的数组，即每个元素都是形如 [start, end] 的区间。

为什么用 LinkedList 而不是 ArrayList？
LinkedList 的 getLast() 方法可以快速获取最后一个元素。
插入新区间的操作更快，因为 LinkedList 直接修改指针，而 ArrayList 可能需要扩容和移动数据。