企业官网建设流程全解析

题41到题45这一组，正好卡在“哈希表—区间—栈”三个知识点交界的位置：最长连续序列考察空间换时间的敏感度，合并区间和插入区间是同一种排序思维的两种变体，用最少数量的箭引爆气球是贪心边界题的经典代表，有效的括号则是栈结构最基础、也最容易在细节上翻车的模板题。这篇就来把这五道题合并复盘，讲清楚每道题的思路动机、代码写法、现场追问和踩坑点，适合正在按面试经典150题逐组刷题、想系统巩固算法与数据结构基本功的人收藏。

1. 题41-题45是“哪五道题”，为什么值得放一起刷

先把题号和组织对清楚。这是面试经典150题列表里的连续5道，分别是：

• 题41：最长连续序列（哈希表 / 集合去重）
• 题42：合并区间（区间归并）
• 题43：插入区间（区间插入 + 归并）
• 题44：用最少数量的箭引爆气球（区间贪心）
• 题45：有效的括号（栈）

1.1 先看整体分类和题目关系

这五道题如果按知识点归类，可以分成三块：

把它们摆在一起看，会发现一个很有意思的事：这五道题表面上各有各的解法，但底层的思考方式高度相似。核心逻辑基本就是三类——去重后找起点、排序后做相邻合并、用栈处理嵌套配对。理解了这三条主线，以后遇到类似题型，即使没见过原题，也能快速给出行之有效的简化路径。

1.2 为什么这个分组对面试复习有价值

很多人刷题喜欢按“难易程度”来，简单题刷了一堆，结果到了面试场上，碰到稍微变形一点的题还是容易发懵。面试经典150题的这种排列，其实是按数据结构和题型难度递进设计的，题41到题45正是从散列思维过渡到区间思维、再过渡到线性结构思维的过程。

我个人的建议是：不要单独看某一道题的代码，而要把它们当一个组合去练。比如合并区间和插入区间，本质上是同一个归并过程，区别只在于插入区间给的是一个已经排序好的输入，只要先想清楚三部分分布，代码不会太难。最长连续序列和有效的括号则分别考察了空间换时间和栈顶匹配的敏感度，这两类功底在算法面试里几乎是必查项。

刷这一组的时候，可以给自己设定一个目标：每道题先想清楚“暴力怎么做”，再想“优化点在哪个维度”。如果能把这几层讲明白，面试官对你的基本功印象会明显不一样。

2. 题41：最长连续序列，用O(n)思路卡住“起点”

2.1 题意和最常见的前置思路

题目要求：给定一个未排序整数数组，返回数字能组成的最长连续序列的长度，而且要求时间复杂度 O(n)。示例是[100,4,200,1,3,2]，最长连续序列是[1,2,3,4]，所以返回 4。

看到未排序数组，第一反应通常是先排序，排完序后从头扫一遍，如果当前数字等于前一个数字跳过，如果是前一个数字加一就累计长度，否则重新计数。这种方法确实简单，但复杂度是 O(n log n)，不满足题目要求。

这里牵涉一个很重要的面试技巧：**哪怕知道最优解，也要先能说出暴力或朴素解法，并准确分析它的复杂度，再去给更优解法。**面试官要看的往往不是你直接默写最优解，而是你有没有完整的比较和取舍过程。

2.2 为什么用哈希集合能做到 O(n)

连续序列要找到最长的一段，关键在于每个连续段从哪里开始。如果数组里存在x-1，那么x一定不可能是这个连续序列的起点。反过来，只有那些“前驱不存在”的元素，才有资格成为一段连续序列的开头。

更具体的做法是：

1. 把所有数字放进一个集合，自动去重。
2. 遍历集合中的每个数字x。
3. 如果x-1也在集合中，说明x不是起点，跳过。
4. 只有x-1不在集合中，才从x开始，不断向后检查x+1、x+2……直到连续段断开。
5. 每次统计完一段长度，更新最大值。

每个元素最多被“向后扫描”一次，因为一段连续序列只会从它的起点开始扫描，所以总体时间复杂度是 O(n)。这里的额外空间复杂度是 O(n)，用空间换取了时间，是典型的以哈希表为核心的解法思路。

用生活例子类比：一群人排成一列长队，你想知道最长的一队有多长，不必每个人挨个数，只需要找“站在最前面的那个人”。没人站在他前面，他才值得作为起点被统计。后边的人虽然也会出现在集合里，但作为起点去统计时只会产生重复计算，直接跳过就好。

2.3 代码实现和最容易翻车的细节

这是实现版本，以 Python 为例：

class Solution: def longestConsecutive(self, nums: List[int]) -> int: num_set = set(nums) longest = 0 for x in num_set: if x - 1 in num_set: continue cur = x length = 1 while cur + 1 in num_set: cur += 1 length += 1 longest = max(longest, length) return longest

代码不长，但有几个细节需要重点注意。

第一，遍历的容器是num_set而不是nums，因为集合去重后，重复元素不会造成重复统计。如果你遍历原数组，碰到重复的数字，会重复判断前驱和向后扫描，虽然最终结果大概率还是对的，但在边界分析和复杂度解释上会显得比较混乱。

第二，在遍历集合的过程中，不要尝试往集合里添加元素或删除元素。虽然这里没这个操作，但类似的题目里很多人会因为想临时记录状态而去修改正在遍历的容器，结果引发运行时错误。面试时如果被问到“能不能原地修改”，应该明确回答：集合的迭代过程中增删元素，语义不确定，应该新建容器或者用其他数据结构保存结果。

第三，空数组的处理要提前说出来。集合为空的情况下，循环不会执行，返回 0，这是符合题意的。

第四，如果题目要求返回最长连续序列本身而不是长度，也不难。可以在内层循环里用一个临时列表收集连续的数字，找到更长的序列时再整体替换。这样空间复杂度会略高一点，但思路是一样的。

2.4 现场追问会怎么变形

面试官在讲完这道题的常规解法后，经常会有几种追问方向：

• 如果数组里有负数，像[-1,0,1,2]，解法还成立吗？成立，因为x-1的判断不限制范围。
• 如果数字范围特别大且很稀疏，怎么办？哈希集合依然适用，因为空间复杂度只跟元素个数有关，和数字跨度无关。
• 如果要求 O(1) 额外空间，可能吗？很难，最优复杂度会退化成排序，面试官如果提这种要求，通常是想测试你是否能正确说明“空间换时间”的取舍。

这里我再补充一个我自己实际测试时会做的小验证：写一个暴力排序解，再写一个优化解，然后用随机数组和边界用例对比结果。不要只靠题目里的示例，因为面试考的是逻辑完整性，随机测几组能帮你发现对去重和起点的误判。

3. 题42：合并区间，排序之后就是一次线性扫描

3.1 题意和第一层理解

题42要求：给定若干区间，合并所有重叠的部分。比如输入[[1,3],[2,6],[8,10],[15,18]]，输出[[1,6],[8,10],[15,18]]。

这道题最关键的认知是：**只要你先按左端点排序，后面的过程就是沿着数组从左往右扫一遍，不断判断当前区间是否和上一个已合并区间重叠。**所有复杂度问题只要卡在排序上，排序是 O(n log n)，之后的扫描是 O(n)。

很多人会困惑：为什么不能直接按右端点排序？也能做，只是合并过程的思维负担更大。按左端点排序时，已合并区间的左端点一定是最小值，你只需要关心右边界需不需要变大；如果按右端点排序，合并时需要维护的东西多一层，代码容易出错。

3.2 归并条件和边界细节

用merged列表保存已经合并好的区间。对于排序后的每个区间interval，有两种情况：

• merged为空，直接把interval放进去。
• 当前区间左端点interval[0]大于merged最后一个区间的右端点merged[-1][1]，说明两者不连续，没有重叠，把当前区间追加进去。
• 否则，说明重叠了，需要把merged[-1][1]更新成max(merged[-1][1], interval[1])。

这里有一个细微但很关键的地方：重叠判断中，merged[-1][1] < interval[0]用的是严格小于。有些题目把“首尾相接”算作重叠，有些题目不算。经典合并区间里，[1,2]和[2,3]按惯例会被合并成[1,3]，因为区间通常是连续覆盖的。遇到具体题目，一定要先看题目如何定义边界。

代码实现：

class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda x: x[0]) merged = [] for interval in intervals: if not merged or merged[-1][1] < interval[0]: merged.append(interval) else: merged[-1][1] = max(merged[-1][1], interval[1]) return merged

3.3 为什么不能只更新一次右边界就完事

很多人第一次写这道题时会不小心把区间左端点也当成会变化的东西，或者在更新右边界时只用当前区间的右边界，而不是用max。但实际情况是，排序后的列表可能存在“大区间包含后面好几个小区间”的情况。比如[[1,10],[2,3],[4,5]]，如果只用当前区间右边界去覆盖，第一次合并会得到[1,10]，但扫描到[4,5]时，如果不取max而直接赋值，右边界可能会变小，逻辑就坏了。

正确的理解是：一旦进入合并状态，你要维护的只是已合并区间的右边界上限，至于左边界在整个合并过程中保持不变，因为它是最早那个区间的左端点，也是整个合并段能取到的最小左端点。

3.4 和排序相关的额外提醒

在 Python 中，sort(key=lambda x: x[0])没问题。但如果面试官要求你写 C++，最好是写：

sort(intervals.begin(), intervals.end());

因为 C++ 对vector<vector<int>>的默认排序按字典序先比较第一个元素，再比较第二个元素，在这个场景下正好可用。如果我现场写，我通常会直接显式写一个 lambda，避免依赖默认排序的行为。

面试中还可能会被追问：

• 如果输入已经有序，这道题还值得讲吗？有价值，要能立刻分析出“已有序时可以 O(n) 完成，但排序已经是 O(n log n)，整体复杂度不变”。
• 能不能原地修改输入？可以，在确认面试官允许修改原数组的前提下，用双指针收缩即可，但没必要，因为代码可读性会变差。

我自己在做这题时有一个固定习惯：先讨论“区间重叠到底是指什么”，再动手。因为区间题最大的坑，永远是对边界的定义不够明确。

4. 题43：插入区间，先想清楚三段式再动手

4.1 题意的特殊之处

题43给定一个已经按左端点排序、且不重叠的区间数组，再给一个新的区间，要求插入到这个数组里，并合并所有必要区间，保证插入后的区间仍然有序且不重叠。比如intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]，插入[4,8]，输出就是[[1,2],[3,10],[12,16]]。

这道题和前一道合并区间最大的区别是：输入不是无序的，而是“半成品”。所以千万不能一上来就无脑排序，否则会浪费它的有序性质，也没有体现出你对题目特征的敏感度。

4.2 三段式分类法

思想上，可以把整个数组分成三部分：

• 第一部分：当前区间的右端点interval[1]小于新区间的左端点newInterval[0]，完全在插入区间左边，不会被影响。
• 第二部分：当前区间和newInterval有重叠，不断更新新区间的左端点和右端点。
• 第三部分：当前区间的左端点interval[0]大于新区间的右端点newInterval[1]，完全在插入区间右边，之后直接按顺序加入。

用代码实现：

class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: res = [] i = 0 n = len(intervals) # 左边没有重叠的部分 while i < n and intervals[i][1] < newInterval[0]: res.append(intervals[i]) i += 1 # 合并所有和 newInterval 重叠的部分 while i < n and intervals[i][0] <= newInterval[1]: newInterval[0] = min(newInterval[0], intervals[i][0]) newInterval[1] = max(newInterval[1], intervals[i][1]) i += 1 res.append(newInterval) # 右边没有被影响的部分 while i < n: res.append(intervals[i]) i += 1 return res

这里的重叠判断用的还是intervals[i][0] <= newInterval[1]。因为区间首尾相接通常会被视作重叠或可以被合并，所以用的是<=，而不是<。具体以题目说明为准，但在这个经典版本里大家默认是合并的。

4.3 为什么推荐先写三段式，而不是直接复用合并区间

有一种偷懒写法是把newInterval直接append进intervals，然后再调用上一题的merge。这种写法在 LeetCode 上能过，而且代码很短。但我不推荐第一次写这道题就直接这么干，原因是：

• 插入一个元素后，数组不再有序，重新排序会破坏题目给的有序输入特性。
• 面试官会追问“你为什么不利用有序性”，这时如果你没想清楚三段式，答不上来就会很尴尬。
• 三段式的边界条件处理更能体现你的代码控制力，比如“新区间完全被包含”“新区间在开头”“新区间在结尾”“新区间跨越多个旧区间”。

这些特殊场景如果通过三段式直接模拟，逻辑自然就能覆盖；如果依赖通用merge，反而容易掩盖细节，导致应付不了变式。

4.4 易错点和个人经验

我实际刷这道题踩过两个坑。

第一个坑是更新newInterval的赋值顺序。在合并循环里，我应该先更新左端点，再更新右端点。但如果左端点更新后，下次循环里又把newInterval[0]拿去和当前区间比较，这时会误以为新区间左端点变大了，从而干扰后续判断。解决办法是：重叠合并的循环条件不要依赖左端点，只用当前区间左端点和新右端点判断。上述代码里我已经用intervals[i][0] <= newInterval[1]作为判断条件，左端点只参与更新，不参与循环条件，这样就安全。

第二个坑是空数组输入。如果intervals是空的，三段式中间部分不会执行，但新区间最终还是会被append进去，逻辑依然正确。这可以作为一道独立用例单独验证。

如果有面试官要求原地优化空间，可以考虑把intervals本身当成结果容器，用两个索引记录预留位置，但可读性会差一些。大多数面试场景下，新建一个结果数组是完全可接受的，面试评分重点在思路清晰，而不是省那点内存。

5. 题44：用最少数量的箭引爆气球，贪心排序维度别选错

5.1 题意和本质

题44给的是一组气球，每个气球用一个区间[x_start, x_end]表示横坐标范围。弓箭沿垂直方向射出，如果一个气球区间内包含箭的 x 坐标，气球就会被引爆。目标是求引爆所有气球所需的最少箭数。

比如points = [[10,16],[2,8],[1,6],[7,12]]，在x=6射一支箭，可以点燃[1,6]和[2,8]；在x=11射一支箭，可以点燃[10,16]和[7,12]，所以答案是 2。

这道题的解法是贪心 + 区间排序，但其本质是“最多有多少个完全不重叠的区间段”，因为一支箭最多只能覆盖一段彼此有交集的气球。如果你按某个规则选一个位置，能覆盖最多气球，就实现了一次“合并覆盖”。整理成结论就是：最少箭数 = 最大不重叠区间数量。

5.2 为什么按右端点排序，而不是按左端点

这是这道题最关键的一个决策点。

如果按左端点排序，你在扫描时看到的第一个区间左端点很靠前，但右端点可能很长，箭放在哪里都可能会浪费对后续气球的覆盖机会。比如[1,10]和[2,3]，按左端点排序，你会先看到[1,10]，箭如果放在 2 到 3 之间可以覆盖[2,3]，但不知道后面还有没有其他交集；如果放在最右端10，就会错过后续右端点较左的气球。

按右端点排序的核心想法是：在当前这批有交集的气球里，选最靠右的那个右端点作为射箭位置，这样既能覆盖当前气球，又能尽可能多地覆盖后面所有左端点不超过这个右端点的气球，贪心策略局部最优，最终得到全局最优。

代码：

class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: if not points: return 0 points.sort(key=lambda x: x[1]) arrow_pos = points[0][1] count = 1 for start, end in points[1:]: if start > arrow_pos: count += 1 arrow_pos = end return count

有一个反直觉的点需要注意：start > arrow_pos用的是严格大于，不是大于等于。因为箭是射在一个坐标点上，如果两个气球的边界刚好相接，比如[1,2]和[2,3]，那么在同一支箭射在x=2时，两个气球都能被引爆。所以只有当前气球的左端点严格大于上一支箭的位置，才必须新增一支箭。

5.3 边界问题和常见的变形追问

空数组返回 0，单气球数组返回 1，这两个边界最好直接想清楚。

面试中这道题最常见的变形是：

• 无重叠区间：给定一组区间，求要移除的最少区间数，使剩余区间互不重叠。思路和箭很像，只是返回的数量逻辑略有不同。
• 会议室安排：给定会议的开始结束时间，求最少会议室数量。本质上是求最大重叠子区间数量，可以用差分数组或排序扫描，但思路和这里不一样。
• 如果你射出箭的位置必须是一个整数，解法如何受影响？经典题意里 x 是实数，如果用整数版本，判断条件可能需要重新审视，但大多数时候区间端点都是整数，区别不大。

我在实际练习时会用一个改进思路：如果允许修改points，可以不用arrow_pos单独存变量，直接复用当前区间的右端点，但在面试讲解时，用独立的变量更清晰。另外，如果面试平台用 C++，排序的 lambda 要注意对long long的减法避免溢出。虽然这里没有使用减法，但类似问题里“两个大整数相减作为比较器返回”是一个经典陷阱，可以主动提到，能加分。

6. 题45：有效的括号，栈处理嵌套配对的标准模板

6.1 为什么用栈，而不是普通数组就能解决

题45要求判断一个只包含(){}[]的字符串是否有效。有效不仅要左括号和右括号一一对应，还要求顺序正确、不交叉。比如([)]虽然每种括号数量是对称的，字符种类也齐全，但括号交叉了，在语义上不合法。

括号嵌套天然是后进先出结构：最后一个出现的左括号，必须第一个遇到右括号并完成配对。这和函数调用栈、文本编辑器里括号高亮、编译器词法分析器的思路是一致的。用栈来保存尚未匹配的左括号，遇到右括号时，栈顶正好是应当匹配的那个左括号，如果匹配成功就弹出，否则直接返回 False。

6.2 代码实现和两个关键判断

先看看实现：

class Solution: def isValid(self, s: str) -> bool: stack = [] pairs = { ')': '(', ']': '[', '}': '{', } for ch in s: if ch in pairs: if not stack or stack[-1] != pairs[ch]: return False stack.pop() else: stack.append(ch) return not stack

这段代码有两大关键判断点。

第一，遇到右括号时，如果栈为空，说明这个右括号没有任何左括号可以和它匹配，立刻返回 False。这个判断漏掉，是初学者最常犯的错误。测试用例"]"会直接暴露这个问题。

第二，如果栈顶和当前右括号对应的左括号不一致，说明交叉嵌套，不是合法的括号组合。比如"([)]"，当遇到]时，栈顶是(，但]对应[，就不匹配，应该直接返回 False。

最后不要忘记，字符串全部扫描完之后，栈必须为空。如果返回True，会漏掉"(","((","(["这类只有左括号的情况。

6.3 栈系列的追问方向和进阶

有效的括号是栈的一道入门题，面试官通常会顺带追问更深一层的题目，比如：

• 给定一个字符串，求最长有效括号子串的长度。那道题就需要结合动态规划或栈位置标记，不是简单的配对弹出。
• 给定一个只包含括号的字符串，求最大嵌套深度。可以直接用一个变量记录当前栈深，遇到左括号加一，右括号减一，过程中取最大值。
• 字符串解码，像"3[a2[c]]"这种题，需要同时用两个栈来保存数字和字符串状态，是括号配对思路的扩展。

如果时间允许，建议在刷完有效括号后，马上做一题最小栈，或者逆波兰表达式求值。这些都能帮你把“栈顶操作”的思想钉死，而不是只会背这一道题的模板。

6.4 关于括号配对策略的补充

括号配对映射表的选择也有一点讲究。我比较习惯把右括号作为 key，这样遇到右括号时，直接查表拿到对应的左括号，和栈顶比较。如果把左括号作为 key，遇到右括号时还需要额外判断当前字符是左还是右，整体也行，但分支会多一些。

面试时，还可以主动说明另一种方法：遇到左括号时，把对应的右括号压入栈；遇到右括号时，直接判断栈顶是否等于当前字符。这个方法的代码也简洁：

class Solution: def isValid(self, s: str) -> bool: stack = [] for ch in s: if ch == '(': stack.append(')') elif ch == '[': stack.append(']') elif ch == '{': stack.append('}') elif not stack or stack.pop() != ch: return False return not stack

两种写法本质相同。第一种需要一张映射表，第二种则把配对关系前置到入栈阶段。我个人建议写法一，因为扩展更多括号类型时，只需修改字典，不用改控制流。

7. 五道题的共性复盘中，有哪些可以直接用的经验

把题41到题45放到一起看，能总结出几个真正对面试有帮助的通用规律。这些规律不仅是针对这几道题，而是可以移植到整个算法与数据结构复习体系里的。

7.1 三条高频解题模式

第一，哈希表的核心用法之一是“空间换时间”。最长连续序列里，我们通过判断前驱是否存在，避免了对每个元素重复统计；两数之和、字母异位词分组、最长连续序列这类题，机理都是把查找从 O(n) 降到了 O(1)。刷到哈希表专题时，要习惯把“值本身”当成一种可以被快速查找的索引，而不是只存计数器。

第二，区间类题目十有八九要先排序。合并区间按左端点排序，射箭题目按右端点排序，无重叠区间也按右端点排序。这里没有固定死路，但面试时如果你能解释“排序维度如何影响后续贪心的覆盖效果”，会比单纯默写答案更有说服力。面试官的反问通常也是“为什么右端点”，所以这个解释一定要自己提前想透彻。

第三，栈的典型应用场景是配对与嵌套。括号、HTML 标签、函数调用栈、表达式求值，本质上都依赖后进先出的语义。遇到这些题，先问自己：当前状态是不是有嵌套关系？如果有，就可以考虑栈。

7.2 实际写代码时最容易踩的几个坑

这几道题虽然难度不一，但代码里的坑是共通的，每一条我都实际踩过：

• 区间题的比较符号容易搞混。合并区间用<表示不连续，插入区间可能要用<=，箭题要用>。写之前先在注释里写清楚“何时需要新增一个元素/区间/箭”，再转成代码。
• 栈题一定要做“空栈安全”检查。无论是入栈还是出栈，都要先考虑栈空的情况。所有栈相关题的基本功，本质上就是“永远不要让空栈被非法访问”。
• 哈希表和集合相关的题，不要在遍历过程中直接修改容器。如果需要记录状态，考虑用额外的变量或另一个容器。
• 返回值类型要看清，是指长度、合并后的区间数组，还是数量。题42和题43都返回二维数组，题44返回整数，代码末尾很容易因为忘记返回类型而漏掉中间逻辑。

7.3 面试表达上的一个小建议

每道题我建议的讲述顺序是：先复述题意和输入输出约束，再说暴力解和复杂度，随后给优化思路，最后写代码并手动走一个稍微复杂的例子。这五道题都有现成的复杂例子，比如最长连续序列可以用负数区间，合并区间可以用全包含例子，括号题可以用交叉括号的示例。手动走过程能让人看出你真的理解，而不是背答案。

尤其对于题44，如果你能主动提醒“这里的排序维度是右端点，因为要尽可能让箭的位置靠右”，面试官通常会对你的贪心理解留下好印象。同样，在题41里，主动讲“我们只从本段序列起点开始统计，所以不会重复计数”也很加分。

7.4 刷完这5道题之后，下一步怎么衔接

题45之后，经典150题列表会进入更复杂的一批栈题，例如简化路径、最小栈、逆波兰表达式求值等。题42到题44的区间思想，也会在后面的“合并 K 个有序链表”“会议室”等变体中反复出现。所以这5道题不只是孤立的题目，它们是为后续的区间贪心和栈应用热身的。

如果你按“每次5题一组”的节奏刷，我个人建议把题41-45整体复盘时间安排在两天内：第一天先独立写出思路和代码，第二天不看答案，直接随机重新做一遍，重点检查刚才说的几个边界条件。实测下来，这种方式比连续刷几十道效果更稳，记忆也更牢固。

最后再分享一个我自己的小习惯：每次刷完一组题，我会把每道题最核心的“一句话思路”写下来，比如题41是“从无前驱的数字作为起点，集合向后扫描”，题44是“按右端点排序，射箭位置尽量靠右”。面试前快速过一遍这些句子，比重新逐行看代码更能恢复现场。希望这一篇题41-45的复盘，能在你的算法面试准备路上帮上一点忙。