企业官网建设流程全解析

前阵子整理贪心算法专题，重新刷到“划分字母区间”这道经典题。说实话，第一次做的时候我完全没把它当贪心题看，按字符串模拟的思路折腾了半天，提交后一堆用例超时。后来想明白核心思路，才发现它其实是“跳跃游戏”那类覆盖式贪心的变体，难度不大，但特别考察对局部最优与全局约束的理解。这篇文章就把我踩过的坑和最终形成的解法拆开讲透，适合刚开始刷贪心题、或者看完答案能 AC 但说不清为什么的读者。顺便说一句，不同题库里这道题的编号可能标得不一样，别纠结题号，搜“划分字母区间”这个名字就好。面试里它经常作为二面算法题出现，面试官喜欢让人讲清楚贪心为什么成立，所以只会背题解远远不够。

1. 这道题让很多人翻车的第一个原因：把“片段最多”理解错了

1.1 题面到底在说什么

题目本身很短：给定一个小写字母字符串 S，把它划分成尽可能多的片段，要求同一个字母只能出现在其中一个片段中，最后返回每个片段长度的列表。

关键点有两个。第一个是“尽可能多”，第二个是“同一个字母只能出现在其中一个片段中”。很多人一看“尽可能多”，下意识就觉得“切得越碎越好”，于是开始想怎么把字符串拆成尽量多的小段。这个直觉不能说错，但会把人带偏。

看标准样例就清楚了：S = "ababcbacadefegdehijhklij"，正确答案是[9, 7, 8]，也就是切成三段："ababcbaca"、"defegde"、"hijhklij"。注意第一段里出现了 a、b、c，这三个字母在整个字符串里出现的位置都被限制在前 9 个字符以内，所以第一片段的右边界至少要到下标 8。第二段里出现了 d、e、f、g，这四个字母在整个字符串里的所有出现又恰好都在下标 9 到 15 之间。第三段同理。

换句话说，这道题要的不是“把一个字符集合能拆得多碎”，而是“在必须把同类元素绑在一起的前提下，最多能分成几组”。一旦某个字母进了某个片段，它在整串中所有出现都必须跟着进这个片段，这就是最硬性的约束。

1.2 常见错误思路和它们的死因

我见过不少人在错误思路上打转，典型的有三种。

第一种是统计字符出现次数，想用次数判断一个片段是否“完整”。比如数出 a 出现 4 次、b 出现 3 次，然后从左往右扫，攒够了数量就尝试切一刀。这种做法看着合理，其实根本站不住脚：约束条件是“位置”，不是“数量”。一个字符即使只出现两次，也可能一个在最左边一个在最右边，把整段都撑开；反过来，一个字符出现很多次，也可能集中在一小段里。用频率做分割依据，本质上是把二维的位置信息压缩成了一维的数量信息，信息量不够，必然出错。

第二种是回溯枚举所有切割方案。先找到所有可能的切割位置，然后用 DFS 或 DP 尝试每一种切法，检查是否满足“同一字母只出现在一个片段”，最后取片段数最多的方案。这个思路在正确性上没问题，但复杂度是灾难性的。长度为 n 的字符串，切割点有 n-1 个，每个点都有“切”和“不切”两种选择，枚举规模是 2^(n-1)。题目给到几百的长度时，这个方案基本等于超时。它更适合作为小规模数据的验证工具，而不适合作为正解。

第三种是在“片段最多”上做文章，想把片段长度切得均匀一点，比如两两配对、前后对称。这种想法属于脑补额外条件。题目只要片段数量最多，不要求长度均匀，你加入均匀性约束，等于给问题加了不存在的限制，答案自然可能出错。

我当初就栽在第二种思路上，以为这题是搜索题，写了两百多行代码，最后还被面试官点了一句“你能不能想想为什么不需要回溯”。后来才意识到，这个问题的约束其实非常强，强到根本不用试错，直接一路贪过去就能得到最优解。

2. 解题灵魂：用每个字母的“最后出现位置”当锚点

2.1 把一个字符的问题翻译成区间问题

想通这道题，首先要换一个角度看。对任意一个字符 ch，它在字符串中第一次出现的位置是 first，最后一次出现的位置是 last。既然“同一个字母只能出现在一个片段里”，那么包含 ch 的片段，右边界无论如何都不可能小于 last。因为如果片段在 last 之前就结束了，ch 在 last 位置又出现了一次，就会被分到后面的片段，违反规则。

进一步想，ch 的约束其实形成了一个天然区间[first, last]。一个合法的片段，要么完整覆盖这个区间，要么和这个区间完全不沾边。所以整个问题可以重新表述成：为字符串里的每个不同字符画一条从首次出现到末次出现的线段，然后把所有相互重叠、相互接触的线段合并，合并后每个区间就是一个片段。

这个视角特别重要，因为它解释了为什么这个问题不需要回溯。每个字符的区间是固定的，不会因为你选择了某种切割方式就改变。既然区间固定，合并的结果就是唯一的，不存在“试了这种切法能得到 3 段、换种切法能得到 4 段”的空间。回溯之所以多余，正是因为答案没有分叉。

2.2 用“不得不扩展”来理解贪心为什么成立

现在只看最后一次出现的位置。假设当前片段的起点是 start，那么第一个字符 S[start] 已经被放入当前片段，它的最后一次出现位置是last[S[start]]，所以当前片段的右边界至少要是这个位置。把 end 初始化成它。

然后从 start 往右扫描。在扫描过程中，每遇到一个字符 ch，就检查它的last[ch]是否比当前的 end 更大。如果更大，说明这个字符在后面还有出现，而它又已经在本片段里出现了，因此本片段的右边界被迫向右扩展到last[ch]。

这个过程很像打包行李：只要箱子里有一件东西后面还要用，你就不能提前封箱；只有把所有已装物品的最后需求都考虑完，才能封箱。这里也一样，end 被不断拉大，直到扫描到 end 位置时发现 end 不再增长，此时才说明“当前已经装入片段的所有字符，它们的最后一次出现都不超出 end”，可以安全切割。

为什么这就是最优？做一个简短的反证。如果存在某个合法切分，它的第一段右边界 r 小于我们算出的 end，那么会有一个字符 x 在本段内出现（假设位置是 k，且 k <= r），而 x 的最后一次出现位置last[x]大于 r。x 在本次出现之后又会在后面出现，于是同一个字母 x 就同时出现在第一段和后面的段，违反了“同一字母只能在一个片段”的条件。也就是说，任何合法切分的首段右边界都不可能小于 end。那我们直接取 end 作为首段右边界，不仅合法，而且不会让可行方案变少。首段确定后，从 end+1 开始继续同样的贪心过程，每一步都是同样的逻辑。局部上“不得不扩展到最大”，全局上也不会吃亏，这就是标准的贪心证明思路。

3. 两遍扫描，代码能短到吓人

3.1 完整代码与逐行解释

代码的核心分两步：第一遍扫描记录每个字符最后一次出现的位置，第二遍扫描维护 end 并在到达 end 时切段。下面是 Python 版本。

class Solution: def partitionLabels(self, s: str) -> List[int]: # 第一遍：记录每个字符最后出现的下标 last = [0] * 26 for i, ch in enumerate(s): last[ord(ch) - ord('a')] = i ans = [] start = 0 end = 0 # 第二遍：从左向右扫描，不断拉大 end，到点切割 for i, ch in enumerate(s): end = max(end, last[ord(ch) - ord('a')]) if i == end: ans.append(end - start + 1) start = end + 1 return ans

这里有一个细节值得注意：第二次循环里end是单调不减的。切完一个片段之后，我没有把end清零，而是让它继续带着旧值参与下一轮的max。很多人第一次看这段代码会疑惑：第二段的 end 起点为什么是 8 而不是 0？实际上旧值不会造成问题，因为下一段只要遇到任何一个字符，它的last就会覆盖旧值；而如果下一段所有字符的 last 都比旧值小，那说明这个片段根本不可能在旧 end 之后合法存在，这种情况不会发生。不过为了自己写代码时思路更清晰，切成ans.append(end - start + 1); start = end + 1之后手动加一句end = i也是完全等价的，只是多写一行而已。

3.2 用标准样例完整推演一遍

还是用官方样例S = "ababcbacadefegdehijhklij"。先看第一遍扫描后记录到的最后出现位置。

然后看第二遍扫描的关键轮次。注意 start 和 end 的联动。

最终得到[9, 7, 8]，和样例一致。整个过程里最值得体会的是：end 并不是一步步涨上去的，而是被某些“拖后腿”的字符一下子拉远。比如第一段的 end 从 0 直接跳到 8，中间 b、c 都没能撼动它；第三段则被 j 直接拉到 23，之后的 h、k、l 全都只是陪跑。

3.3 边界用例：空串、单字符、全同、全异

边界情况能暴露很多实现问题，建议刷完这道题后把这几个用例都过一遍。

• 空串""：第一遍循环不执行，第二遍也不执行，直接返回[]。Python 里last数组全是 0，不会报错。

• 单字符"a"：last['a'] = 0，第二遍 i=0 时 end 从 0 变 0，切出[1]。

• 全相同字符"aaaa"：last['a'] = 3，end 一上来就是 3，直到 i=3 才切割，返回[4]。这个用例特别能纠正“片段多 = 切得碎”的错误直觉，无论怎么切，a 的出没范围都要求它只能在一个片段里，所以整串必须是一段。

• 全不同字符"abcdef"：每个字符的 last 都等于自己的下标，于是每轮 i == end，切出[1,1,1,1,1,1]。这是片段数量的理论上限，因为没有字符会在后面重复出现，约束形同虚设。

• 再来一个反直觉的"caacb"：c 的最后位置是 2，a 的最后位置是 3，b 的最后位置是 4。第二遍扫描时，i=0 时 end 被 c 拉到 2，i=1 时 a 把 end 拉到 3，i=2 时 c 不能动 end，i=3 时 a 也不能动 end，但 i=4 时 b 把 end 拉到 4，此时才切割，整体返回[5]。这说明 b 虽然只出现一次，但因为它出现在下标 4，就把整个段拖满了。一个字符哪怕只出现一次，只要位置靠后，同样能成为片段的边界锚点。

4. 复杂度、边界条件和面试官的连环追问

4.1 时间与空间复杂度算给你看

时间复杂度是 O(n)，n 是字符串长度。第一遍遍历记录 last，第二遍遍历扫描切段，每一轮都是常数操作，所以总开销是 2n 的量级。

空间复杂度这里值得多说一句。如果按“哈希表存字符下标”来理解，空间是 O(σ)，σ 是字符串中不同字符的个数。但由于题目限制为小写字母，σ 最大只有 26，所以严格来说空间是 O(1)。如果面试时你回答“空间复杂度 O(n)”，大概率会被追问：存储的是字符串长度的量还是字符类型的量？用固定数组而不是字典，一眼就能看出空间和字符串长短无关，这也是很多人推荐数组写法的原因。

原题字符串只含小写字母，所以数组版本里用ord(ch) - ord('a')做索引很安全。如果题目条件放宽，允许大写字母甚至任意 Unicode 字符，那就改成字典last = {}，思路完全不变，只是空间从固定 26 变成按字符种类增长。用字典的版本我会写成：

last = {} for i, ch in enumerate(s): last[ch] = i

查询时end = max(end, last[ch])即可。这类题目用字典反而更通用，面试官问起来也更好解释。

4.2 面试官爱问的 5 个问题

我汇总了几个常见的追问，建议提前想清楚回答，不要卡壳。

1. 为什么不能一趟扫描就完成？ 因为切片的边界取决于“某个字符未来还会不会出现”，而未来信息只有在扫描到末尾之后才知道。第二遍扫描本质上是在“全知”的状态下做决策，这是离线算法。如果只允许一趟扫描，相当于流式处理，单凭当前位置和过往位置无法判断一个字符是否已经全部出现完。所以预处理 last 这一步不是优化，而是必要前提。

2. 切完一段之后 end 要不要清零？ 清零不清零结果一样。我在代码里倾向于不清零，利用max的单调性省一行。但如果你笔试时怕解释不清楚，可以在切段后写end = i，效果等价。重点是你得知道这两者为什么等价，而不是死记某一种写法。

3. 原题返回长度，如果想返回片段内容怎么办？ 改成ans.append(s[start:end+1])就行。返回内容和返回长度在切割点上没有任何区别，只是存储的数据类型不同，面试官这么问通常是想确认你是否理解了切片区间是闭区间。

4. 如果字符串包含大写字母或者中文字符呢？ 用字典替代固定数组，每个字符的最后出现位置照常记录。算法的时间复杂度仍是 O(n)，空间复杂度变成 O(σ)，不再能说 O(1)。

5. 为什么这道题归类为贪心而不是模拟？ 因为每一段的右边界都是“当前必须扩展到的最大位置”，这一步选择不回溯、不试错，直接根据全局信息和当前状态做局部最优决策，而且能证明局部最优累积成全局最优。这正是贪心算法的定义特征。模拟通常指按规则机械推进，不涉及这种“最优性论证”。

5. 和合并区间、跳跃游戏放在一起看，思路一下就通了

5.1 从区间合并视角重新审视这道题

我前面提到，把每个字符映射成[first, last]的区间后，问题就变成区间合并。这里补一个更重的写法，虽然不如贪心简洁，但特别适合用来理解等价关系。

def by_intervals(s): first = {} last = {} for i, ch in enumerate(s): if ch not in first: first[ch] = i last[ch] = i intervals = [(first[ch], last[ch]) for ch in first] intervals.sort() merged = [] for l, r in intervals: if not merged or l > merged[-1][1]: merged.append([l, r]) else: merged[-1][1] = max(merged[-1][1], r) return [r - l + 1 for l, r in merged]

这个版本的复杂度包含一个排序，整体是 O(σ log σ + n)。由于 σ 很小，实际也很快。但它最大的价值是让你看到一个事实：每个字符的首次出现和末次出现固定以后，所有区间的并集和重叠关系是客观存在的。贪心解法其实就是在这个区间合并的基础上，利用“字符串从左到右的顺序天然是区间起点顺序”来省掉排序。想通了这一点，面试的时候不管面试官从哪个角度切入，你都能接住。

5.2 与跳跃游戏 II 的类比

力扣的跳跃游戏 II 是另一个让我印象深刻的覆盖型贪心。在那道题里，你在每个位置 i 能跳到的最大距离是i + nums[i]，当前跳跃能覆盖的边界之内，你不断更新“下一步能到达的最远位置”，到达边界后步数加一。

这道题几乎一模一样。每个字符 ch 的last[ch]就是一个“绝对坐标下的最远落点”，你在当前片段的边界内扫描时，不断用last[ch]更新“本片段最终能到达的最远位置”，到达边界后切一刀、计一段。区别只是跳跃游戏关注“最少跳几次”，这里关注“最多切几段”；跳跃游戏里每一步有多个可选落脚点，这里每个位置只有一个字符、一个 last 值。模式识别一旦建立，下次遇到“给你一堆元素，每个元素有约束范围，问能分成几组”的题，第一反应就应该是覆盖式贪心。

5.3 现实业务里的映射

这类“按元素最大跨度分组”的问题在工程里其实有影子。比如日志清洗时，一个请求会分成多行日志输出，我们想把同一个请求 ID 的所有日志行聚合到一个切片里，就需要先统计每个请求 ID 最后出现的行号，然后按行号切分。再比如广告投放里，需要把同一个用户在某个时间窗内的所有触达记录归并成一个会话，同样是“同类元素只能在同组”的约束。算法题的价值很多时候不在于它本身，而在于它训练你看到“相同结构”的能力。一个能在字符串上快速抽象出覆盖区间的人，面对这些业务问题也会本能地去找“每个元素的最后出现位置”。

6. 我踩过的坑和一套自测方法

6.1 三个容易写错的实现细节

第一，start更新错位置。切成start = end而不是start = end + 1。看着只差一个 1，但会导致下一个片段的起点和上一个片段的终点重叠，片段长度全部错乱。这种 bug 在样例"a"上可能测不出来，因为end - start + 1会变成负值，样例一跑直接崩，反而算好事。

第二，使用字典时误把“首次出现位置”当“最后出现位置”。有朋友为了省一次遍历，在第二遍循环里用last.get(ch, i)来更新 end，得出的 end 会偏小。因为get只会在键不存在时返回 i，而键存在时返回的是第一遍记录的旧值，这其实就是想要的值。但如果不小心写成last[ch] = i再取last[ch]，那就把字典在第二遍里又改了一遍，最后得到的是当前位置而不是末次位置。我在帮人 review 代码时见过这种写法，很隐蔽，建议写完立刻用"ababcbacadefegdehijhklij"自测。

第三，数组索引忘减字符偏移。比如写last[ord(ch) - 97]，没问题；但写成last[ch]或者last[ord(ch)]会直接越界或者取到错误位置。这类问题最有效的预防方式是统一用一个常量表示ord('a')，或者直接写成ord(ch) - ord('a')，可读性更好。

6.2 用暴力枚举脚本交叉验证

刷题最怕“脑补正确”。我现在的习惯是，遇到这种贪心题，先写一个暴力枚举版本用于小规模测试，再用随机数据对拍。下面这个暴力版穷举了所有切割方案，只适合长度很小的字符串，但用来验证贪心正确性非常够用。

from itertools import combinations def brute(s): n = len(s) best_len = 0 best = None for k in range(1, n + 1): for cuts in combinations(range(1, n), k - 1): segs = [] prev = 0 for c in cuts + (n,): segs.append(s[prev:c]) prev = c char_sets = [set(seg) for seg in segs] ok = True for i in range(len(char_sets)): for j in range(i + 1, len(char_sets)): if char_sets[i] & char_sets[j]: ok = False break if not ok: break if ok and len(segs) > best_len: best_len = len(segs) best = [len(seg) for seg in segs] return best or []

对拍的时候可以随机生成小写字母组成的短字符串，长度控制在 1 到 12，因为暴力枚举的量级是 2^(n-1)。比如生成 200 组随机样例，把partitionLabels和brute的结果逐一对比。我最初写出来的贪心代码一直正确，但有一次随机生成到"caacb"这类数据时，我才真正注意到 b 这种“只出现一次但位置靠后”的字符也能拖动整段边界。这个发现比单纯 AC 更有价值，因为它帮我建立了对覆盖式贪心的直觉。

6.3 一个有效的学习习惯：看看“最远的那个字符”

现在遇到任何区间分组、覆盖型问题，我会习惯性地问自己三个问题：每个元素的最后位置是多少？当前组必须覆盖到的最远点是多少？到达这个最远点时，能不能安全收拢？如果三个问题都有明确答案，那大概率就不需要回溯或动态规划。

这道“划分字母区间”给我最大的启发，不是那十几行代码，而是“片段最多”和“切得碎”之间的微妙差别。真正想让片段数量多，反而要让每个片段尽量长地把同类约束吸收干净，把一个字母的所有出现都捂在同一个片段里。这个经验和直觉，后来在处理很多资源分组、任务分区的问题时都用得上。刷题刷到最后，记住的不是题号，而是这种“看问题结构”的方式。