- 正确答案：合并升序区间是指给定一组已按左端点升序排列的闭区间（如 [1,3], [2,6], [8,10], [15,18]），将所有重叠或相邻的区间合并为不相交的最简区间集合。例如上述输入合并后为 [[1,6], [8,10], [15,18]]。核心操作是遍历一次，维护当前合并区间的左右边界，对每个新区间判断是否可合并（即新区间左端点 ≤ 当前右边界），若可则更新右边界，否则将当前区间加入结果并重置为新区间。 - 解答思路：由于输入已按左端点升序排序，因此只需单次线性扫描即可完成合并，无需排序预处理。初始化当前合并区间为第一个区间；从第二个区间开始遍历，对每个区间 interval = [l, r]： - 若 l <= current_right，则说明与当前区间重叠或相邻（注意：题目中“升序区间”通常默认为闭区间，相邻如 [1,2] 和 [2,3] 是否合并取决于题意——标准 LeetCode 56 题要求合并相邻区间，即允许等号）； - 否则，将当前合并区间加入结果，重置 current_left = l, current_right = r； - 若可合并，则 current_right = max(current_right, r)； - 最后别忘记将末尾未加入的 current 区间 append 到结果中。 - 深度知识讲解： 1. 底层数据结构依赖：输入为 vector> 或 List[int[2]]，本质是二维数组，访问 O(1)，但内存连续性影响缓存友好性；若用链表则遍历仍 O(n)，但随机访问退化，故实际工业代码必用动态数组。 2. 时间复杂度：O(n)，严格单遍扫描，无嵌套循环；空间复杂度 O(1) 额外空间（不计输出存储），属原地合并的变体（虽需输出空间，但无辅助栈/队列）。 3. 稳定性与边界条件：算法不改变相对顺序（因输入已序），但合并本身无“稳定性”概念；关键边界包括空输入、单区间、全重叠（如 [[1,4],[2,3],[3,6]] → [[1,6]]）、全不重叠、左端点相同（如 [[1,2],[1,5]] → [[1,5]]）、右端点小于左端点（非法输入，但健壮实现应校验）。 4. 实现原理本质是贪心策略：每次尽可能向右延展当前区间，因为左端点已排序，后续任何区间都不可能与更早的区间产生“跨当前”的可合并性（即若 interval[i] 无法与 current 合并，则 interval[i+1] 的左端点 ≥ interval[i].left ≥ current.right + 1，必然也无法合并），故贪心选择安全。 5. 扩展思考：若输入未排序，必须先按 left 排序，时间升至 O(n log n)；若需支持动态插入区间并实时合并，可用平衡 BST（如 C++ set> 维护不重叠区间，插入时二分查找邻近区间再合并，单次 O(log n)）；若区间为开区间或半开区间（如 [1,3) 和 [3,5) 是否合并？），需明确定义“相邻”语义——数学上开区间 [a,b) 与 [b,c) 不相交，但业务中常按整数坐标视为可接续，此时应统一转换为闭区间或自定义比较逻辑。 - 代码示例（C++ 风格伪代码，含注释）： vector> merge(vector>& intervals) { if (intervals.empty()) return {}; // 输入保证升序，故跳过 sort(intervals.begin(), intervals.end()); vector> result; int current_left = intervals[0][0]; int current_right = intervals[0][1]; for (int i = 1; i < intervals.size(); ++i) { int l = intervals[i][0]; int r = intervals[i][1]; if (l <= current_right) { // 可合并：重叠或相邻（闭区间下 l == current_right 即相邻） current_right = max(current_right, r); // 右边界取最大，覆盖嵌套情况如 [1,5] 和 [2,3] } else { result.push_back({current_left, current_right}); current_left = l; current_right = r; } } result.push_back({current_left, current_right}); // 加入最后一组 return result; } - 补充：Python 版本中需注意 list 的不可变性，但逻辑完全一致；Java 中需使用 ArrayList；若面试官追问“如何验证输入是否真有序”，可补充一次遍历校验：for i=1 to n-1: assert intervals[i][0] >= intervals[i-1][0]，否则抛异常或自动排序。 - 常见陷阱提醒：忽略最后一个区间 push；混淆重叠判断条件（写成 l < current_right 而非 <=，导致相邻区间未合并）；未处理空输入；max 函数误用（如写成 current_right = r 而非 max）；修改原数组而非新建 result（破坏输入契约）。

快手后端实习二面

全站热榜

创作者周榜