LeetCode 763中等贪心 · 最后位置
划分字母区间 图解题解
这道题到底在问什么
把字符串划分成尽可能多的片段，使每个字母最多出现在一个片段中，返回每个片段长度。
- s
- "ababcbacadefegdehijhklij"
- 输出
- [9,7,8]
先想最直接的笨办法
这类题不是枚举所有切法，而是维护当前片段必须覆盖到的最远位置。（动画第 15 步）
最优解：一步一步想明白
- 3先记每个字符最后出现位置，当前片段的 end 是这些最后位置的最大值。
- 4贪心关键：一段必须装下段内每个字母的所有出现，所以只要覆盖到每个字母最后一次出现的下标即可。
- 5i=0 是 a，last(a)=8 → 段尾 end=8，这一段至少要延到下标 8。
- 6i 一路扫到 7：途中 b(last5)、c(last7)、a 的最后位置都 ≤ 8，end 不变。
- 7i 走到 8，正好 i == end：从这里切开，第一段 [0,8] 长度 9。
- 8新段从 d 开始，last(d)=14 → end=14。
- 9看到 e，last(e)=15 比当前 end=14 更远 → end 被推到 15。这就是“边扫边把段尾扩到最远”的核心。
- 10i=15 == end，切第二刀：第二段 [9,15] 长度 7。
- 11第三段从 h 起，i/j 把 end 一路推到 23（j 最后在 23），扫到 23 == end 收尾。
- 12三段长度 [9, 7, 8]，每段都恰好覆盖段内字母的最后出现位置。
- 15这类题不是枚举所有切法，而是维护当前片段必须覆盖到的最远位置。
⚠️ 容易写错的地方
✗ 错：看到重复字母就立刻切
✓ 对：必须等 i == end 才能切
片段内任一字母后面还出现，就不能结束
✗ 错：只看当前字符的位置
✓ 对：end 取所有已见字符 last 的最大值
后看到的字符可能把边界推得更远
完整代码（Python / C++ / Java）
Python
class Solution:
def partitionLabels(self, s):
last = {ch: i for i, ch in enumerate(s)}
ans = []
start = end = 0
for i, ch in enumerate(s):
end = max(end, last[ch])
if i == end:
ans.append(end - start + 1)
start = i + 1
return ansC++
class Solution {
public:
vector<int> partitionLabels(string s) {
int last[26] = {0};
for (int i = 0; i < s.size(); i++) last[s[i] - 'a'] = i;
vector<int> ans;
int start = 0, end = 0;
for (int i = 0; i < s.size(); i++) {
end = max(end, last[s[i] - 'a']);
if (i == end) {
ans.push_back(end - start + 1);
start = i + 1;
}
}
return ans;
}
};Java
class Solution {
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> ans = 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) {
ans.add(end - start + 1);
start = i + 1;
}
}
return ans;
}
}套路模板 · 最后位置贪心
# 划分字母区间骨架 · 最远边界贪心
last = {字母 -> 它最后出现的下标}
start = end = 0
for i, ch in enumerate(s):
end = max(end, last[ch]) # 段尾扩到当前字母最远处
if i == end: # i 追上段尾 -> 这一段闭合
记录长度 end - start + 1
start = i + 1复杂度
时间复杂度
O(n)
扫两遍字符串（建表 + 划分），共约 2n
空间复杂度
O(1)
last 表最多 26 个字母，常数额外空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 划分字母区间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么记“最后位置”而不是出现次数？+
一段必须包含段内每个字母的全部出现；只要覆盖到每个字母最后一次出现的下标，前面的出现自然都在段内。
为什么 i==end 就能安全切？+
说明 [start,i] 内所有字母的最后出现都 ≤ i，后面不会再冒出来，切开后两段互不含相同字母。
复杂度？+
两遍线性扫描 O(n)；last 表最多 26 项，O(1) 额外空间。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。