在刷 LeetCode 的过程中“合并区间” 是一道经典的区间类题目这道题不仅考察对区间排序、遍历逻辑的理解还要求在时间和空间复杂度上做到高效优化。今天就来分享这道题的高效解法核心思路是先将区间按左端点升序排列再通过遍历逐步合并重叠区间最终实现时间复杂度 O(n·log n)、空间复杂度 O(log n) 的最优解完美契合题干要求的解题思路。题目描述给你一个区间数组 intervals 其中 intervals[i] [starti, endi] 请你合并所有重叠的区间并返回一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间。要求按照题干思路实现优化时间和空间复杂度。解题思路核心思想是排序遍历合并先通过排序让区间按左端点升序排列确保后续遍历过程中只需对比当前区间与已合并区间的右端点即可判断是否重叠无需回头对比从而提升遍历效率同时控制空间复杂度。具体核心思路贴合题干要求1. 排序预处理我们先将区间数组按照左端点升序排列这是合并区间的前提——排序后所有可能重叠的区间会相邻后续只需顺序遍历即可完成合并避免无序区间带来的重复对比。2. 遍历合并操作我们先将第一个区间加入答案初始时答案数组为空先暂存第一个区间后续逐步加入数组然后依次考虑之后的每个区间分两种情况处理- 若答案数组中最后一个区间的右端点小于当前考虑区间的左端点说明两个区间无重合直接将当前区间加入答案数组末尾- 否则说明两个区间存在重合我们需要用当前区间的右端点更新答案数组中最后一个区间的右端点将其置为二者的较大值实现区间合并。3. 结果返回遍历结束后答案数组中存储的就是所有合并后的不重叠区间直接返回即可。具体步骤边界判断若输入的区间数组为空直接返回空数组避免无效遍历。区间排序将区间数组 intervals 按照每个区间的左端点升序排列排序的时间复杂度为 O(n·log n)空间复杂度为 O(log n)对应题干要求。初始化答案列表创建一个列表 res 用于存储合并后的区间先将排序后的第一个区间加入 res对应题干“先将第一个区间加入答案”的逻辑。遍历区间从排序后的第二个区间开始依次遍历每个区间 current intervals[i]。判断合并取出 res 中最后一个区间 last res.get(res.size()-1)对比 last 的右端点与 current 的左端点若 last[1] current[0]无重叠将 current 直接加入 res 末尾若 last[1] ≥ current[0]有重叠更新 last[1] 为 max(last[1], current[1])完成区间合并。遍历结束后将 res 列表转换为数组返回该数组即为最终结果。复杂度分析时间复杂度O(n·log n)其中 n 是区间数组的长度。核心耗时在于区间排序排序的时间复杂度为 O(n·log n)后续遍历区间的操作是 O(n)整体时间复杂度由排序主导即为 O(n·log n)。空间复杂度O(log n)此处指的是排序过程中产生的递归栈空间默认排序算法为快速排序其空间复杂度为 O(log n)。题目中用于存储结果的答案列表 res通常不计入额外空间复杂度题干也明确此空间可忽略因此整体空间复杂度为 O(log n)符合题干要求。Java 代码public int[][] merge(int[][] intervals) { // 按照左边界升序排序 Arrays.sort(intervals, Comparator.comparingInt(a - a[0])); Listint[] res new ArrayList(); // left 是第一个区间的左边界right 是第一个区间的右边界 int left intervals[0][0], right intervals[0][1]; for (int i 1; i intervals.length; i) { // start 是当前考虑区间的左边界end 是当前考虑区间的右边界 int start intervals[i][0], end intervals[i][1]; if (right start){ // 区间不重叠在此放入 res.add(new int[]{left, right}); left start; right end; }else { right Math.max(right, end); } } // 用于放入最后一个区间 res.add(new int[]{left, right}); return res.toArray(new int[res.size()][]); }代码解析初始化与边界判断边界判断if (intervals null || intervals.length 0) return new int[0][0]; 应对区间数组为空的极端情况直接返回空数组避免后续空指针异常和无效遍历。区间排序Arrays.sort(intervals, (a, b) - a[0] - b[0]); 使用 lambda 表达式指定排序规则按照每个区间的左端点a[0]、b[0]升序排列这是合并区间的核心前提。遍历与合并操作Listlt;int[]gt; res new ArrayList(); res.add(intervals[0]); 初始化答案列表先将排序后的第一个区间加入对应题干“先将第一个区间加入答案”的逻辑。for (int i 1; i intervals.length; i)从第二个区间开始遍历因为第一个区间已加入答案列表无需重复处理。int[] current intervals[i]; 取出当前正在考虑的区间int[] last res.get(res.size() - 1); 取出答案列表中最后一个已合并的区间用于判断是否重叠。判断逻辑if (last[1] current[0])若已合并区间的右端点小于当前区间的左端点说明两个区间无重叠直接将当前区间加入答案列表末尾。else若有重叠将已合并区间的右端点更新为“自身右端点”与“当前区间右端点”的最大值确保合并后的区间能覆盖两个重叠区间的所有范围。返回结果return res.toArray(new int[res.size()][]); 将存储合并后区间的列表转换为二维数组并返回符合题目要求的返回类型。示例验证以输入 intervals [[1,3],[2,6],[8,10],[15,18]] 为例逐步验证解题过程1. 排序后intervals [[1,3],[2,6],[8,10],[15,18]]本身已按左端点升序排序后不变。2. 初始化 res [[1,3]]。3. 遍历过程i1current [2,6]last [1,3]last[1] 3 ≥ current[0] 2重叠更新 last[1] max(3,6) 6res 变为 [[1,6]]。i2current [8,10]last [1,6]last[1] 6 current[0] 8无重叠将 current 加入 resres 变为 [[1,6],[8,10]]。i3current [15,18]last [8,10]last[1] 10 current[0] 15无重叠将 current 加入 resres 变为 [[1,6],[8,10],[15,18]]。最终返回 res 转换后的数组 [[1,6],[8,10],[15,18]]符合预期结果。再验证重叠较多的情况输入 intervals [[1,4],[4,5]]排序后为 [[1,4],[4,5]]遍历 i1 时last[1] 4 ≥ current[0] 4更新 last[1] max(4,5) 5最终返回 [[1,5]]正确合并区间。总结这道题的核心是“排序预处理顺序遍历合并”通过排序让重叠区间相邻再通过简单的遍历判断即可高效完成合并同时实现时间和空间的最优。关键点总结贴合题干思路排序是前提按区间左端点升序排列确保所有可能重叠的区间相邻避免无序区间带来的重复对比为后续遍历合并奠定基础。合并逻辑简洁仅需对比当前区间与已合并区间的右端点分“重叠”和“不重叠”两种情况处理无需复杂操作遍历一次即可完成。复杂度控制到位排序的时间复杂度 O(n·log n)、空间复杂度 O(log n)遍历的时间复杂度 O(n)整体符合题干要求的最优复杂度。这种“排序遍历”的思路不仅适用于本题还可以迁移到其他区间类题目中如“插入区间”掌握这种思路能有效提升区间类题目的解题效率希望能帮助大家理解和掌握