题目描述
思路解析动画文字版
两个变量:end 是「当前这段必须延伸到的最远处」,start 是「这段的起点」。i 追上 end 就切一刀。
先扫一遍,把每个字母最后一次出现的下标记下来:a→3 b→4 c→2 d→5 e→8 f→7。划分时全靠它决定一段要拉多长。
指针 i 走到下标 0,这一格是字母 a。a 最后一次出现在下标 3,看看要不要把这段拉长。
字母 a 还会延伸到下标 3,比原来的终点 0 远,所以把这段拉长到 3。
指针 i 走到下标 1,这一格是字母 b。b 最后一次出现在下标 4,看看要不要把这段拉长。
字母 b 还会延伸到下标 4,比原来的终点 3 远,所以把这段拉长到 4。
指针 i 走到下标 2,这一格是字母 c。c 最后一次出现在下标 2,看看要不要把这段拉长。
字母 c 最后出现在 2,没超过现在的终点 4,这段终点不变,还是 4。
指针 i 走到下标 3,这一格是字母 a。a 最后一次出现在下标 3,看看要不要把这段拉长。
字母 a 最后出现在 3,没超过现在的终点 4,这段终点不变,还是 4。
指针 i 走到下标 4,这一格是字母 b。b 最后一次出现在下标 4,看看要不要把这段拉长。
字母 b 最后出现在 4,没超过现在的终点 4,这段终点不变,还是 4。
指针 i 正好走到 end(4 = 4),说明这一段里所有字母都收尾了,在这切一刀。这段从 0 到 4,长度 5。
指针 i 走到下标 5,这一格是字母 d。d 最后一次出现在下标 5,看看要不要把这段拉长。
字母 d 最后出现在 5,没超过现在的终点 5,这段终点不变,还是 5。
指针 i 正好走到 end(5 = 5),说明这一段里所有字母都收尾了,在这切一刀。这段从 5 到 5,长度 1。
指针 i 走到下标 6,这一格是字母 e。e 最后一次出现在下标 8,看看要不要把这段拉长。
字母 e 还会延伸到下标 8,比原来的终点 6 远,所以把这段拉长到 8。
指针 i 走到下标 7,这一格是字母 f。f 最后一次出现在下标 7,看看要不要把这段拉长。
字母 f 最后出现在 7,没超过现在的终点 8,这段终点不变,还是 8。
指针 i 走到下标 8,这一格是字母 e。e 最后一次出现在下标 8,看看要不要把这段拉长。
字母 e 最后出现在 8,没超过现在的终点 8,这段终点不变,还是 8。
指针 i 正好走到 end(8 = 8),说明这一段里所有字母都收尾了,在这切一刀。这段从 6 到 8,长度 3。
整串扫完,一共切出 3 段,长度依次是 5、1、3,这就是最终答案。
三个高频追问:两个变量含义、为何先求 last、以及全不重复的边界。
参考代码
def partitionLabels(s): last = {c: i for i, c in enumerate(s)} # 每个字母最后下标 res = [] start = end = 0 for i, c in enumerate(s): end = max(end, last[c]) # 拉长当前段终点 if i == end: # 追上终点 → 切一刀 res.append(end - start + 1) start = i + 1 return res复杂度
- 时间:O(n),一遍记录最后下标、一遍扫描划分,每个字符只看常数次
- 空间:O(1),last 表最多 26 个小写字母,是固定大小,不随 n 增长
易错点
面试追问把动画讲成自己的话
追问start 和 end 分别代表什么?
追问为什么先求每个字母的最后下标?
追问如果整个字符串里每个字母都互不相同,结果是什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
有效的括号字符串
LeetCode 678 · 中等 · 沿着 贪心 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题