图解算法通识讲义线性结构
数组区间合并与快速选择
核心心智模型：锚定左界，贪心吃进；按起点升序排序，连续重叠区间平滑熔断吞并。
核心交互式算法图解演练沙盒
区间合并模型
区间排序与贪心重叠融合演练
步骤 1 / 4
正在审视区间:[2, 6]
先排序 O(N log N) + 线性扫描 O(N)合并结果集 Merged Intervals
[1, 3]
重叠探测：当前区间 [2, 6] 的起点 2 <= 前一区间 [1, 3] 的终点 3，存在重叠！
关键操作与时空复杂度速查对照表
| 操作 / 算法阶段 | 平均时间 | 最坏时间 | 空间复杂度 | 核心底层机制 |
|---|---|---|---|---|
| 区间合并总耗时 | O(N log N) | O(N log N) | O(N) | 瓶颈在于对区间左端点的全量排序。 |
| 快速选择单值定位 | O(N) | O(N^2) | O(log N) | 每次递归排除一半，N + N/2 + N/4 = 2N。 |
template.java
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] interval : intervals) {
if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
merged.add(interval);
} else {
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
}
}
return merged.toArray(new int[merged.size()][]);解题核心心法提炼
- 所有区间调度、区间合并问题，80% 的第一步都是「排序」，排好序后问题立刻退化为简单的一维线性贪心。
- 快速选择在数组求第 K 大中比小顶堆更加高效（平摊 O(N) vs 堆的 O(N log K)）。
常见踩坑警示与避坑指南
- 排序比较器中直接使用 a[0] - b[0] 在负数区间可能引发整数溢出。
对应 Hot 100 实战题目突围
原理已掌握！立即进入沉浸式工作台开始实战演练，强化代码肌肉记忆