LeetCode 763中等贪心 · 最后位置
划分字母区间 图解题解
这道题到底在问什么
给定字符串 s，把它划分成尽可能多的片段，使每个字母最多出现在一个片段中。返回每个片段的长度。
- 输入
- s = "abcabdefe"
- 输出
- [5,1,3]（切成 abcab | d | efe 三段）
最优解：一步一步想明白
- 3两个变量：end 是「当前这段必须延伸到的最远处」，start 是「这段的起点」。i 追上 end 就切一刀。
- 4先扫一遍，把每个字母最后一次出现的下标记下来：a→3 b→4 c→2 d→5 e→8 f→7。划分时全靠它决定一段要拉多长。
- 5指针 i 走到下标 0，这一格是字母 a。a 最后一次出现在下标 3，看看要不要把这段拉长。
- 6字母 a 还会延伸到下标 3，比原来的终点 0 远，所以把这段拉长到 3。
- 7指针 i 走到下标 1，这一格是字母 b。b 最后一次出现在下标 4，看看要不要把这段拉长。
- 8字母 b 还会延伸到下标 4，比原来的终点 3 远，所以把这段拉长到 4。
- 9指针 i 走到下标 2，这一格是字母 c。c 最后一次出现在下标 2，看看要不要把这段拉长。
- 10字母 c 最后出现在 2，没超过现在的终点 4，这段终点不变，还是 4。
- 11指针 i 走到下标 3，这一格是字母 a。a 最后一次出现在下标 3，看看要不要把这段拉长。
- 12字母 a 最后出现在 3，没超过现在的终点 4，这段终点不变，还是 4。
- 13指针 i 走到下标 4，这一格是字母 b。b 最后一次出现在下标 4，看看要不要把这段拉长。
- 14字母 b 最后出现在 4，没超过现在的终点 4，这段终点不变，还是 4。
- 15指针 i 正好走到 end（4 = 4），说明这一段里所有字母都收尾了，在这切一刀。这段从 0 到 4，长度 5。
- 16指针 i 走到下标 5，这一格是字母 d。d 最后一次出现在下标 5，看看要不要把这段拉长。
- 17字母 d 最后出现在 5，没超过现在的终点 5，这段终点不变，还是 5。
- 18指针 i 正好走到 end（5 = 5），说明这一段里所有字母都收尾了，在这切一刀。这段从 5 到 5，长度 1。
- 19指针 i 走到下标 6，这一格是字母 e。e 最后一次出现在下标 8，看看要不要把这段拉长。
- 20字母 e 还会延伸到下标 8，比原来的终点 6 远，所以把这段拉长到 8。
- 21指针 i 走到下标 7，这一格是字母 f。f 最后一次出现在下标 7，看看要不要把这段拉长。
- 22字母 f 最后出现在 7，没超过现在的终点 8，这段终点不变，还是 8。
- 23指针 i 走到下标 8，这一格是字母 e。e 最后一次出现在下标 8，看看要不要把这段拉长。
- 24字母 e 最后出现在 8，没超过现在的终点 8，这段终点不变，还是 8。
- 25指针 i 正好走到 end（8 = 8），说明这一段里所有字母都收尾了，在这切一刀。这段从 6 到 8，长度 3。
- 26整串扫完，一共切出 3 段，长度依次是 5、1、3，这就是最终答案。
⚠️ 容易写错的地方
✗ 错：切段时只看当前字母、不维护全段最远终点 end
✓ 对：end 取「途中所有字母最后下标」的最大值
段内某个字母还会在后面出现，不拉长 end 会把一个字母切到两段里
✗ 错：用 i == last[当前字母] 当切点
✓ 对：用 i == end 当切点
当前字母可能早早收尾，但段里别的字母还没收尾，必须等 end
✗ 错：切完忘了把 start 移到 i+1
✓ 对：切一刀后 start = i + 1
start 不更新，下一段的长度会从旧起点算，全部偏大
完整代码（Python / C++ / Java）
Python
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 resC++
vector<int> partitionLabels(string s){
int last[26] = {0};
for (int i = 0; i < s.size(); i++) last[s[i]-'a'] = i;
vector<int> res;
int start = 0, end = 0;
for (int i = 0; i < s.size(); i++) {
end = max(end, last[s[i]-'a']);
if (i == end) { res.push_back(end - start + 1); start = i + 1; }
}
return res;
}Java
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) last[s.charAt(i)-'a'] = i;
List<Integer> res = new ArrayList<>();
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, last[s.charAt(i)-'a']);
if (i == end) { res.add(end - start + 1); start = i + 1; }
}
return res;
}复杂度
时间
O(n)
一遍记录最后下标、一遍扫描划分，每个字符只看常数次
空间
O(1)
last 表最多 26 个小写字母，是固定大小，不随 n 增长
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 划分字母区间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
start 和 end 分别代表什么？+
start 是当前这段的起点下标；end 是当前这段「必须延伸到」的最远下标，会随段内字母的最后出现位置不断右移。i 追上 end 时切段。
为什么先求每个字母的最后下标？+
划分时一旦遇到某字母，就必须把这段拉到它最后出现的位置，否则会把同一字母切进两段。提前算好 last，扫描时 O(1) 查。
如果整个字符串里每个字母都互不相同，结果是什么？+
每个字母只出现一次，end 每步都等于 i，于是每个字符各成一段，返回全是 1、个数等于字符串长度。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 划分字母区间 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。