- 正确答案：给定一个按起始位置升序排列的区间列表，合并所有重叠或相邻的区间，返回合并后的不重叠区间列表。例如输入 [[1,3],[2,6],[8,10],[15,18]]，输出 [[1,6],[8,10],[15,18]]；输入 [[1,4],[4,5]]，输出 [[1,5]]（注意：[1,4] 和 [4,5] 是相邻区间，端点相接，题目通常要求合并）。 - 解答思路： 1. 首先确认输入已按 intervals[i][0]（左端点）升序排序——题干明确“有序区间”，故无需额外排序，这是关键前提；若未排序则需先 O(n log n) 排序。 2. 初始化结果列表 res，将第一个区间加入作为当前待合并区间 current = intervals[0]。 3. 从第二个区间开始遍历：对每个 interval，判断是否与 current 重叠或相邻：若 interval[0] <= current[1]（注意：≤ 表示重叠或右端紧邻左端），则可合并，更新 current[1] = max(current[1], interval[1])；否则，将 current 加入 res，并令 current = interval。 4. 遍历结束后，将最后一个 current 加入 res。时间复杂度：O(n)，仅一次线性扫描；空间复杂度：O(1)（不计输出空间）。 - 深度知识讲解：本题本质考察对“区间关系”的数学建模能力与贪心策略的应用。底层核心是理解两个闭区间 [a,b] 和 [c,d]（a≤b, c≤d）的合并条件：当且仅当 c ≤ b 时二者可合并（因已排序，必有 a ≤ c，故只需检查左区间右端是否 ≥ 右区间左端）。此处“≤”包含两种情况： - 重叠：c < b（如 [1,5] 和 [3,7]） - 相邻：c == b（如 [1,4] 和 [4,5]）→ 合并为 [1,5]，符合数学上闭区间的连续性定义。贪心正确性证明：因输入已排序，对于任意前缀已合并的区间 current = [L,R]，若下一个 interval = [c,d] 满足 c ≤ R，则 [L,R] 必须与 [c,d] 合并——否则存在更早的、未被合并的覆盖机会，违背局部最优即全局最优的贪心选择性质。进阶考点延伸： - 若输入无序，需先排序，此时比较器需稳定处理：sort(intervals.begin(), intervals.end(), [](const vector& a, const vector& b) { return a[0] < b[0]; })；若左端相同，按右端降序排可简化逻辑（但非必须）。 - 边界鲁棒性：需考虑空输入、单区间、全重叠（如 [[1,2],[2,3],[3,4]] → [[1,4]]）、整数溢出（若区间值极大，max 操作需注意，但 LC 数据范围安全）。 - 空间优化：可原地合并（in-place），用双指针：slow 指向当前合并区间的写入位置，fast 遍历，避免新建 res 数组（但输出仍需新空间，实际意义有限）。 - 扩展场景：动态区间合并（如数据流中持续插入新区间，需支持 O(log n) 插入+合并 → 可用平衡BST维护不重叠区间集合，如 C++ std::map, void> 或 Java TreeMap）。 - 代码示例（C++，清晰版）： vector> merge(vector>& intervals) { if (intervals.empty()) return {}; vector> res; vector current = intervals[0]; for (int i = 1; i < intervals.size(); ++i) { if (intervals[i][0] <= current[1]) { current[1] = max(current[1], intervals[i][1]); } else { res.push_back(current); current = intervals[i]; } } res.push_back(current); return res; } - 代码示例（Python，一行式逻辑等价，含注释）： def merge(intervals): if not intervals: return [] res = [] current = intervals[0] for i in range(1, len(intervals)): if intervals[i][0] <= current[1]: # 可合并：重叠或相邻 current[1] = max(current[1], intervals[i][1]) else: res.append(current) current = intervals[i] res.append(current) return res

快手电商llm日常实习一面 55min

全站热榜

创作者周榜