：万流归宗——「合并区间」)
哈喽各位，我是前端L。
欢迎来到贪心算法专题第十四篇！
题目很简单：给你一堆乱序的区间，比如 [1,3], [8,10], [2,6], [15,18]。
请你把重叠的区间合并。
[1,3]和[2,6]重叠，合并后变成[1,6]（取最小起点，最大终点）。[8,10]和[15,18]没人理它们，保持原样。最终输出：
[[1,6], [8,10], [15,18]]。
力扣 56. 合并区间
https://leetcode.cn/problems/merge-intervals/
题目分析：
输入：
intervals数组。输出：合并后的数组。
核心思维：排序 + 动态更新右边界
依然是老套路：先按 Start 排序。
排序后：[1,3], [2,6], [8,10], [15,18]。
贪心策略：
我们将第一个区间放入结果集 result 中作为**“当前正在合并的区间”**。
然后遍历后面的区间：
重叠了？(
当前.start <= 结果集中最后一个.end)不需要新增区间。
合并操作：我们要把结果集里那个区间的右边界撑大。
新的右边界 =
Math.max(结果集.end, 当前.end)。注意：这里取 Max，因为我们要尽可能包含更多的范围（合并）。这与“射气球”取 Min（找交集）正好相反。
没重叠？
说明当前结果集里的那个区间已经合并完毕，无法再向后延伸了。
直接把当前区间 push 进结果集，作为新的“正在合并对象”。
算法流程 (JavaScript)
特判：长度为 0 或 1 直接返回。
排序：
intervals.sort((a, b) => a[0] - b[0])。初始化：
result = [intervals[0]]。遍历：从
i = 1开始。取出
result的最后一个元素last。取出当前遍历元素
cur。如果
cur[0] <= last[1](有重叠)：last[1] = Math.max(last[1], cur[1])（直接修改 result 里的元素）。
否则：
result.push(cur)。
返回
result。
代码实现
JavaScript
/** * @param {number[][]} intervals * @return {number[][]} */ var merge = function(intervals) { if (intervals.length === 0) return []; // 1. 按左边界从小到大排序 intervals.sort((a, b) => a[0] - b[0]); // 初始化结果集，先把第一个放进去 const result = [intervals[0]]; // 2. 从第二个开始遍历 for (let i = 1; i < intervals.length; i++) { let cur = intervals[i]; // 获取结果集中“当前正在合并”的那个区间（也就是最后一个） let last = result[result.length - 1]; // 判断是否重叠 // 当前区间的左边界 <= 上一个区间的右边界 if (cur[0] <= last[1]) { // 发现重叠！执行合并 // 只需要更新右边界，左边界肯定是用 last[0] (因为它更小，排序保证的) // 右边界要取两者中最大的，这样才能包住两个区间 last[1] = Math.max(last[1], cur[1]); } else { // 没有重叠，直接放入结果集 result.push(cur); } } return result; };深度辨析：区间三兄弟总结
这三道题（452射气球, 435无重叠, 56合并）是区间问题的“三驾马车”。它们的第一步永远是Sort by Start。
区别在于处理重叠时的贪心决策：
| 题目 | 目标 | 重叠时的操作 | 边界更新策略 |
| 452. 射气球 | 找公共交集 | 箭数不变，范围变小 | end = Math.min(取交集) |
| 435. 无重叠 | 丢弃区间 | 移除数+1，保留短的 | end = Math.min(为了不挡路) |
| 56. 合并区间 | 融合区间 | 区间数不变，范围变大 | end = Math.max(取并集) |
记住这个表格，区间问题就通关了！
复杂度分析
时间复杂度：O(N log N)
瓶颈在排序。遍历只是 O(N)。
空间复杂度：O(N)
需要一个
result数组来存储结果（如果那是返回值不算额外空间，则是 O(log N) 的排序栈空间）。
下一题预告：单调递增的数字
区间问题到此结束！ 接下来我们要处理一道非常有意思的数字逻辑题。
给定一个非负整数
N。找出小于或等于
N的最大整数，同时这个整数每一位上的数字都要是单调递增的。比如
N = 10-> 输出9。比如
N = 1234-> 输出1234。比如
N = 332-> 输出299。
这道题的贪心策略在于：一旦发现某一位比后面一位大（破坏了单调性），就得把这一位减 1，然后把后面所有位都变成 9。就像做借位减法一样。
准备好玩数字了吗？下期见！
