LeetCode 补拙笔记

0. 前言

• 日期：2026.06.20
• 题目：56. 合并区间
• 难度：中等
• 标签：数组、排序、贪心

1. 题目理解

问题描述 给定二维数组 intervals 表示若干区间 [start, end]，合并所有存在重叠或相接的区间，返回由不重叠区间组成的二维数组，覆盖全部原始区间范围。

示例

输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：[1,3]与[2,6]重叠合并为[1,6]，其余区间互不重叠直接保留。

输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间端点相接视为重叠，需要合并。

2. 解题思路

核心观察

1. 区间无序无法直接判断重叠，必须按区间左端点升序排序；
2. 排序后仅需对比当前区间左端点与上一个合并区间右端点：
   • 当前左端点 ≤ 上一个右端点：区间重叠，更新上一区间右端点为两者最大值；
   • 当前左端点 > 上一个右端点：无重叠，直接新增区间。
3. 原版代码使用flag、单独初始化首尾变量、多段if判断；优化方案使用List动态保存合并结果，循环统一处理全部区间，消除冗余分支。

算法步骤

1. 特判空数组直接返回空结果；
2. 将区间数组按左端点升序排序；
3. 创建集合存储合并后的区间；
4. 遍历每一个区间：
   • 集合为空 或 当前区间与最后合并区间无重叠，直接加入集合；
   • 存在重叠则更新集合最后区间的右端；
5. 集合转为二维数组返回。

3. 代码实现

package lc0_lc99.lc56;
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
    public int[][] merge(int[][] intervals) {
        ArrayList<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int left = intervals[0][0];
        int right = intervals[0][1];
        int index = 0;
        boolean flag = true;
        for (int i = 1; i < intervals.length; i++) {
            if (right >= intervals[i][0]) {
                if (intervals[i][1] > right) {
                    right = intervals[i][1];
                }
            } else {
                res.add(new int[]{left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        res.add(new int[]{left, right});

        int[][] res1 = res.toArray(new int[0][]);
        return res1;
    }
}

4. 代码优化说明

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
class Solution {
public int[][] merge(int[][] intervals) {
    // 特判空输入
    if(intervals.length == 0){
        return new int[0][2];
    }
    // 按区间起点升序排序
    Arrays.sort(intervals, new Comparator<int[]>(){
        public int compare(int[] intervals1, int[] intervals2){
            return intervals1[0] - intervals2[0];
        }
    });
    List<int[]> merged = new ArrayList<>();
    for(int i = 0; i < intervals.length; i++){
        int left = intervals[i][0], right = intervals[i][1];
        // 集合空 或 无重叠直接新增，否则更新右端，仅一层if-else
        if(merged.size() == 0 || merged.get(merged.size()-1)[1] < left){
            merged.add(new int[]{left, right});
        }else{
            merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], right);
        }
    }
    return merged.toArray(new int[merged.size()][]);
}
}

5. 复杂度分析

• 原始实现 时间复杂度：$O(n\log n)$，排序为主要耗时；循环拆分首区间单独初始化，嵌套if判断较多 空间复杂度：$O(n)$，集合存储合并区间，排序栈开销$O(\log n)$
• 优化实现 时间复杂度：$O(n\log n)$，排序耗时不变；统一循环处理所有区间，消除内层嵌套if，分支更少 空间复杂度：$O(n)$，结果集合占用，无多余临时标记变量（flag、index、单独left/right初始化）

6. 总结

• 核心：区间排序 + 贪心合并，排序后仅需和上一个合并区间对比；
• 优化亮点：统一循环逻辑，取消单独初始化首区间、多余flag标记；使用Math.max替代内层if更新右端，减少分支层级；
• 边界要点：输入为空、区间端点相接（如[1,4]、[4,5]）同样需要合并。