平时刷算法题的时候,不少朋友碰到区间合并这类题目都会犯难。看着代码不长,却搞不懂每一行为什么要这么写,也分不清不同函数、写法之间的区别,还容易踩各种小坑。
今天不光讲解题思路,还会把每一行代码拆开细说,包括语法规则、变量作用、替换写法和需要留意的细节,全程不跳步骤,慢慢把逻辑捋清楚。
一、先聊聊题目本身
先说说我们要解决的问题:给定一组由整数组成的区间列表,把其中相互重叠、首尾相接的区间合并到一起,最后输出合并完成后的新区间。
举个很生活化的小例子帮大家理解: 想象你手上有几张记录时间的便签,分别写着「1 点 - 3 点」「2 点 - 6 点」「8 点 - 10 点」「15 点 - 18 点」。一眼就能看出来,前两张便签的时间是重叠的,完全可以合成一张「1 点 - 6 点」;后面两张时间互不干扰,就保留原样。放到代码里,这就是典型的区间合并场景。
如果这些便签乱序摆放,你就得来回翻看比对,特别麻烦。所以我们第一反应就是先把便签按起始时间排好顺序,之后顺着往下整理就行,这也是这道算法题最核心的思路。
二、完整代码总览
先把整段代码放出来,后面我们再逐行拆解分析。
classSolution:defmerge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda p: p[0]) ans = []for p in intervals:if ans and p[0] <= ans[-1][1]: ans[-1][1] = max(ans[-1][1], p[1])else: ans.append(p)return ans
三、逐行代码详细讲解
第 1 行
classSolution:
这行代码作用是定义一个名为 Solution 的类。
在力扣这类算法平台上,题目统一要求用「类 + 内部方法」的格式提交代码,这个类名是固定的,不能随意修改。你可以把它简单理解成一个存放解题方法的容器。
读法:将类名 Solution 进行定义。 补充:Python 中 class 是定义类的固定关键字,书写时后面必须加冒号,下一行代码要做好缩进。
第 2 行
defmerge(self, intervals: List[List[int]]) -> List[List[int]]:
这一行是在 Solution 类里面,定义核心解题方法 merge,我们拆分来看:
def 是 Python 定义函数 / 方法的关键字,merge 是方法名,同样是平台规定好的名称;
self 是类中实例方法的第一个固定参数,代表类本身,属于语法要求,不能省略;
intervals: List[List[int]] 是类型注解,意思是传入的参数 intervals 是一个嵌套列表,列表里的每一个子列表都是整数,对应我们的区间数据;
读法:定义名为 merge 的方法,参数包含 self 和 intervals,方法返回值为整数嵌套列表。 小提醒:使用 List 类型注解,需要提前导入对应模块,算法平台一般会默认帮我们处理。
第 3 行
intervals.sort(key=lambda p: p[0])
这一步就是我们前面说的「给区间排序」,也是解题的关键一步。
sort() 是 Python 列表自带的方法,特点是原地修改原列表,不会生成新列表,相比 sorted() 更节省内存;
lambda p: p[0] 是匿名函数,p 代表每一个区间,p[0] 代表区间的第一个元素(区间左端点)。整句含义就是:按照每个区间的左端点从小到大排序。
读法:对 intervals 列表执行排序操作,排序规则为取每个元素的第 0 位。
补充说明:
为什么不用 p[1]?p[1] 是区间右端点,按右端点排序会打乱整体逻辑,无法正常合并区间;
替代写法:可以不用匿名函数,单独写一个普通函数,效果完全一致:
defget_left(p):return p[0]intervals.sort(key=get_left)
第 4 行
ans = []
这是基础的赋值语句,把右侧的空列表,赋值给左侧变量 ans。
ans 是英文 answer 的简写,也是写代码时常用的变量名,作用是存放最终合并完成的区间结果。一开始列表为空,后续我们会不断往里面添加数据。
读法:将空列表赋值给变量 ans。 补充:也可以写成 ans = list(),二者效果相同,日常写法里 [] 会更简洁。
第 5 行
for p in intervals:
这是 Python 标准的 for 循环语句,作用是遍历已经排好序的 intervals 列表。
循环里的变量 p,每一轮都会依次代表列表里的一个区间。靠着这个循环,我们就能逐个处理所有区间。
读法:遍历 intervals 中的每一个元素,并用变量 p 接收当前元素。 小坑提醒:不要让循环变量和外部变量重名,容易把原有数据覆盖。
第 6 行
if ans and p[0] <= ans[-1][1]:
这是核心判断条件,用来检查当前区间是否需要和已有区间合并,我们拆开理解:
ans:Python 里空列表判定为假,非空列表判定为真。ans 写在最前面,是为了先判断结果列表是否有数据,避免列表为空时读取元素报错;
and 是逻辑与,只有前后两个条件同时成立,整体才为真;
ans[-1] 代表 ans 列表里最后一个元素,也就是上一个已经整理好的区间;ans[-1][1] 就是这个区间的右端点;
p[0] <= ans[-1][1]:代表当前区间的左端点,小于等于上一个区间的右端点,说明两个区间重叠或者首尾相接,需要合并。
读法:如果 ans 列表不为空,并且当前区间左端点小于等于 ans 最后一个区间的右端点。
重点避坑:
不能把判断顺序写反,一旦先读取 ans[-1][1],空列表会直接触发索引报错;
要用 <= 而不是 =,否则首尾相接的区间会被判定为不重叠。
第 7 行
ans[-1][1] = max(ans[-1][1], p[1])
满足合并条件时,执行这行代码,依旧是赋值语句,右侧计算结果赋值给左侧。
max() 是 Python 内置函数,作用是取出两个数值里更大的那一个;
因为区间已经按左端点排好序,合并后左端点不用改动,只需要更新右端点。取两个区间右端点的最大值,就能完整覆盖重叠部分。
读法:将 ans 最后一个区间的右端点,更新为原有右端点和当前区间右端点中的较大值。
为什么不能直接写成 ans[-1][1] = p[1]? 如果当前区间的右端点更小,直接赋值会把合并后的区间缩短,造成结果错误,所以必须使用 max() 函数。
第 8 行
else:
配合上方 if 使用的分支语句,意思是:当 if 里的判断条件不成立时,就执行 else 下方的代码。
出现这种情况一般有两种可能:一是结果列表 ans 还是空的(第一次循环);二是当前区间和上一个区间没有重叠、互不相连。
第 9 行
ans.append(p)
append() 是列表内置方法,作用是把括号里的内容整体作为一个元素,添加到列表末尾。
这里就是把当前完整区间 p,直接新增到结果列表里。
读法:将元素 p 追加到 ans 列表的末尾。
避坑提醒:千万别写成 ans += p,这个写法会把区间拆分成单个数字塞进列表,破坏嵌套列表的格式。
第 10 行
return ans
return 是函数返回语句,作用是把变量 ans 里存储的最终结果输出,同时结束整个方法的运行。
读法:返回变量 ans 的值。
四、完整运行流程模拟
我们拿一组实际数据 [[1,3],[2,6],[8,10],[15,18]],顺着代码走一遍流程,加深理解:
代码先对区间按左端点排序,本组数据本身有序,无需变动;
第一个区间 [1,3]:ans 为空,执行 append,此时 ans = [[1,3]];
第二个区间 [2,6]:区间重叠,更新右端点,此时 ans = [[1,6]];
第三个区间 [8,10]:无重叠,直接追加,此时 ans = [[1,6],[8,10]];
第四个区间 [15,18]:无重叠,直接追加,最终 ans = [[1,6],[8,10],[15,18]];
五、补充:另一种等价写法
除了上面的基础版本,这里再分享一种思路不同、逻辑同样通顺的写法,大家可以对比参考:
classSolution:defmerge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda p: p[0])ifnot intervals:return [] ans = [] current_start, current_end = intervals[0][0], intervals[0][1]for start, end in intervals[1:]:if start <= current_end: current_end = max(current_end, end)else: ans.append([current_start, current_end]) current_start, current_end = start, end ans.append([current_start, current_end])return ans
这个版本用单独变量记录当前正在合并的区间,不用反复读取列表最后一位,逻辑会更直白,两种写法没有优劣,看个人使用习惯即可。
结尾
以上就是区间合并这道题的全部讲解啦,从解题思路、生活案例,到每一行代码的语法、作用、坑点都梳理完了。
如果看完觉得内容对你有帮助,不妨点个赞支持一下。后续也会继续分享这类细致的代码讲解内容,我们一起慢慢学、慢慢练~