LeetCode 763. 划分字母区间——字符最后位置贪心的变体
LeetCode 763. 划分字母区间——字符最后位置贪心的变体
适读人群：Java初中级工程师、算法进阶学习者 | 阅读时长：约18分钟 | 难度：中等
开篇故事
这道题让我想起工作中遇到的一个微服务拆分问题。我们有一堆功能模块，每个模块和某些特定资源绑定，要求同一个资源不能跨服务——换句话说，使用了相同资源的模块必须分在同一个服务里。问题是：怎么把模块划分成尽可能多的独立服务，同时保证没有资源跨服务？
这不就是字母划分区间的问题吗？每个字母代表一种资源，字母出现的范围代表资源被使用的区间，我们要把字符串切割成尽可能多的片段，每种字母只在一个片段里出现。
这道题的贪心思路非常优雅：只需要记录每个字母最后出现的位置，然后用"区间延伸"的贪心方式逐步确定每个分割点。今天我们把这个思路讲透，同时把它和前面几道区间题联系起来，你会发现它们本质上都是"区间合并"的变体。
一、题目解析
题目： 给你一个字符串 s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s。返回一个表示每个字符串片段的长度的列表。
示例：
- 输入：s = "ababcbacadefegdehijhklij"
- 输出：[9,7,8]
- 解释：划分结果为 "ababcbaca"、"defegde"、"hijhklij"。每个字母最多出现在一个片段中。
关键约束： 划分结果要能重新拼成原字符串（保持顺序），不能打乱。
本质转化：
每个字母的"活动范围"是 [first_occurrence, last_occurrence]。每个片段必须包含一个字母的完整范围（从它第一次出现到最后一次出现）。这样，"划分字母区间"等价于"合并所有活动范围有交叉的字母的区间"——跟 LeetCode 56 合并区间几乎一模一样！
区别：LeetCode 56 是给定区间列表合并，本题需要先从字符串中提取每个字母的区间，然后合并。
二、解法一：提取区间后合并（等价于 LeetCode 56）
思路
两步走：
- 统计每个字母的 [first, last] 区间。
- 对区间按 first 排序，然后合并重叠区间（与 LeetCode 56 完全相同），记录每个合并后区间的长度。
代码
import java.util.*;
public class Solution_IntervalMerge {
public List<Integer> partitionLabels(String s) {
int n = s.length();
int[][] intervals = new int[26][2];
// 初始化：-1表示该字母未出现
for (int i = 0; i < 26; i++) {
intervals[i][0] = Integer.MAX_VALUE;
intervals[i][1] = Integer.MIN_VALUE;
}
// 统计每个字母的首次和末次出现位置
for (int i = 0; i < n; i++) {
int c = s.charAt(i) - 'a';
intervals[c][0] = Math.min(intervals[c][0], i);
intervals[c][1] = Math.max(intervals[c][1], i);
}
// 过滤未出现的字母，收集有效区间
List<int[]> valid = new ArrayList<>();
for (int[] interval : intervals) {
if (interval[0] != Integer.MAX_VALUE) {
valid.add(interval);
}
}
// 按 first 排序
valid.sort((a, b) -> a[0] - b[0]);
// 合并区间，记录每段长度
List<Integer> result = new ArrayList<>();
int start = valid.get(0)[0], end = valid.get(0)[1];
for (int i = 1; i < valid.size(); i++) {
if (valid.get(i)[0] <= end) {
// 重叠，扩展右边界
end = Math.max(end, valid.get(i)[1]);
} else {
// 不重叠，记录当前段长度
result.add(end - start + 1);
start = valid.get(i)[0];
end = valid.get(i)[1];
}
}
result.add(end - start + 1); // 最后一段
return result;
}
}复杂度分析
- 时间复杂度： O(n + 26 log 26) = O(n)，统计 O(n)，排序 O(1)（字母表只有26个字母）。
- 空间复杂度： O(26) = O(1)，固定大小的字母表数组。
三、解法二：只记最后位置的贪心（经典O(n)解法）
思路
优化的关键洞察：由于字符串是从左到右扫描的，我们不需要记录每个字母的"首次出现位置"，只需要记录"最后出现位置"。
扫描时，维护"当前片段的右边界"——这个边界初始化为当前字母的最后出现位置，然后随着我们向右扫描，不断更新为遇到的所有字母的最后出现位置的最大值。
一旦当前扫描位置 i 等于右边界，就找到了一个切割点。
正确性证明：
- 右边界右侧的所有字母，它们的最后出现位置也在右边界右侧（否则右边界就不是这个值了）。
- 右边界及其左侧的所有字母，它们的最后出现位置都在右边界及其左侧（这正是右边界的定义）。
- 因此，在 i == end 时切割，左侧的所有字母完整包含在当前片段中，右侧的字母完整包含在后续片段中。切割是合法的。
- 每次尽可能早地切割（在满足条件的最早位置切割），保证片段数尽可能多。这就是贪心的"多切"策略。
代码
import java.util.*;
public 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> result = new ArrayList<>();
int start = 0; // 当前片段的起始位置
int end = 0; // 当前片段的右边界（动态扩展）
for (int i = 0; i < s.length(); i++) {
// 更新右边界：扩展到当前字母最后出现的位置
end = Math.max(end, last[s.charAt(i) - 'a']);
// 如果当前位置恰好是右边界，找到一个切割点
if (i == end) {
result.add(end - start + 1);
start = i + 1; // 下一片段从 i+1 开始
}
}
return result;
}
}Mermaid 图：贪心过程
复杂度分析
- 时间复杂度： O(n)，两次线性扫描。
- 空间复杂度： O(26) = O(1)，固定大小数组。
四、解法三：滑动窗口视角（统一框架）
思路
从滑动窗口的视角来看：维护一个窗口 [start, end]，窗口的右边界 end 不断扩展（遇到当前字母的最后位置就扩展），直到 i 追上 end，窗口关闭，记录长度，开启新窗口。
这和解法二是同一个算法，只是换了个表述方式，但这个"窗口"视角更容易在面试中说清楚。
import java.util.*;
public class Solution_Window {
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 windowStart = 0;
int windowEnd = 0;
for (int i = 0; i < s.length(); i++) {
// 将窗口右边界扩展到当前字母的最后位置（如果更大的话）
windowEnd = Math.max(windowEnd, last[s.charAt(i) - 'a']);
// 当指针到达窗口右边界，当前窗口就是一个合法片段
if (i == windowEnd) {
ans.add(windowEnd - windowStart + 1);
windowStart = windowEnd + 1; // 开启新窗口
// windowEnd 会在下次循环中被更新
}
}
return ans;
}
}复杂度分析
与解法二完全相同：O(n) 时间，O(1) 空间。
五、举一反三
字符频率+区间类型题
LeetCode 1229. 安排会议日程（类似变体） 给两个人各自的空闲时间段，找到一个公共的长度 >= duration 的时间段。双指针匹配两个排好序的区间列表。
LeetCode 2405. 子字符串的最优划分（相似思路） 将字符串划分为最多的子串，使每个子串中不含重复字符。滑动窗口记录当前窗口内字符的最后出现位置。
区间类贪心题的统一视角
本题 = 字母区间合并（等价LeetCode 56）+ 贪心切割
LeetCode 56 = 区间按start排序 + 合并重叠区间
LeetCode 435 = 区间按end排序 + 贪心保留最多不重叠
LeetCode 452 = 区间按end排序 + 贪心找最少覆盖点这四道题都是"区间"问题，共享同一个底层思维：对区间排序，然后贪心处理。区别在于目标不同（合并 vs 切割 vs 选取 vs 覆盖），导致排序维度和贪心方向有所差异。
六、踩坑实录
坑一：最后一段没有加入结果
解法一（区间合并方案）中，for 循环只在"发现不重叠"时记录上一段，最后一段需要在循环外单独添加。
// 错误：循环内只处理"不重叠"情况，最后一段丢失
for (...) {
if (not overlap) { result.add(end - start + 1); ... }
else { ... }
}
// 修复：循环后补充最后一段
result.add(end - start + 1);坑二：解法二中 end 初始化为 0
当 i=0，first_char 最后出现在某个位置，end 被更新。但如果 end 初始化为 -1 或其他值，可能导致逻辑错误。初始化为 0 是正确的（因为 i 从 0 开始，end 不会比 i 小）。
坑三：字符串大小写处理
题目保证只含小写字母，所以 s.charAt(i) - 'a' 正确。如果输入可能含大写字母，需要用 Character.toLowerCase() 或扩展数组到 52。
坑四：把片段"长度"当作"结束位置"返回
题目要求返回每个片段的长度，不是结束位置。片段长度 = end - start + 1（不是 end - start）。这个 +1 经常被忘掉。
坑五：对"尽可能多的片段"的理解偏差
"尽可能多"意味着每次要尽早切割——一旦 i 追上了右边界，立刻切割，不要等到更晚。我们的算法在 i == end 时立刻切割，这保证了片段数最大化。
七、总结
划分字母区间是一道把"合并区间"思想应用到字符串场景的优雅题目。两步走：记录每个字母的最后位置，然后用扩展窗口+贪心切割，一次线性扫描搞定。
与 LeetCode 56 的本质联系：
本题 = 先提取字母区间 + 合并重叠区间 + 记录合并后的长度
而解法二的优化在于：不需要显式构造区间列表，在扫描过程中动态维护当前窗口的右边界，边扫描边切割。
| 解法 | 时间复杂度 | 空间复杂度 | 关键思想 |
|---|---|---|---|
| 提取区间后合并 | O(n) | O(1) | 等价LeetCode 56 |
| 只记最后位置 | O(n) | O(1) | 动态右边界扩展 |
| 滑动窗口视角 | O(n) | O(1) | 窗口到右边界时切割 |
补充深入讲解：划分字母区间的数学原理与拓展应用
字母区间问题的本质：连通性与等价类
从集合论的角度来看，划分字母区间的本质是将字符串中的字符分成若干"等价类"，使得同一等价类中的字符必须在同一片段中。
两个字符"必须同片段"的条件是：它们的活动范围有重叠（直接或间接）。"直接重叠"意味着两个字母的区间有交叉；"间接重叠"意味着通过第三个字母的区间可以联通。
例如 s = "abca"，字母 a 的范围是 [0,3]，字母 b 的范围是 [1,1]，字母 c 的范围是 [2,2]。a 的范围覆盖了 b 和 c 的整个范围，所以 a、b、c 必须在同一片段。而如果后面有字母 d 仅在 [5,5] 出现，则 d 不与 a、b、c 共享范围，可以在单独的片段。
这种"通过区间重叠建立连通性"的思想，与图论中的"连通分量"完全对应：将每个字母看作一个节点，如果两个字母的区间重叠则连边，最终的划分就是这个图的各个连通分量。
贪心算法（动态右边界扩展）实际上是在计算这个图的连通分量，而且是一次线性扫描就完成，效率比显式建图更高。这是贪心算法将"复杂图问题"简化为"线性扫描问题"的又一个典型案例。
只记最后位置而不记最前位置的原因
这道题只需要记录每个字母的最后出现位置（last[]数组），而不需要记录首次出现位置。这是为什么？
原因在于：我们是从左到右扫描字符串，当我们扫描到位置 i 时，字母 s[i] 的首次出现位置一定在 i 或 i 的左边（因为我们是顺序扫描）。如果字母 s[i] 首次出现位置在当前片段起始位置 start 之后，那它的区间完全在 [start, last[s[i]]] 内，已经被我们的右边界扩展所覆盖。
而最后出现位置才是真正的"边界约束"：如果一个字母的最后出现位置在当前右边界之后，说明我们需要把右边界扩展到那个位置，才能保证这个字母完整地在当前片段内。
所以，只用最后位置就足够了。这是贪心设计的精妙之处：识别出"真正有约束力的信息"（最后位置），而忽略"可以推导的信息"（首次位置）。
动态右边界的正确性证明
我们的算法维护一个动态右边界 end，每扫描一个字符就用它的最后位置更新 end（取较大值）。当扫描位置 i 恰好等于 end 时，[start, i] 就是一个合法片段。
为什么这是正确的？需要证明两件事：
第一，[start, i] 内的所有字母，其最后出现位置都在 i 之前（或等于 i）。如果不是，假设某个字母的最后出现位置 > i，那么在扫描到那个字母时，end 一定会被更新为 > i，与 end = i 矛盾。因此第一点得证。
第二，i+1 之后的所有字母，其最后出现位置都在 i 之后。如果不是，假设位置 j > i 的字母 c，其最后出现位置 lc <= i，那么 c 也出现在 [start, i] 内（因为 j > i 但 lc <= i，意味着 c 的活动范围是 [first_c, lc] 并且 first_c >= start 且 j 在 [start, i] 内，矛盾于 j > i）。
两点合在一起，说明 [start, i] 是一个"自包含"的片段，之后的字符不会出现在这个片段内，这个片段的切割是合法的。
变形：如何找到字符最少的合法划分？
本题要求"尽可能多的片段"，等价于每次在最早可能的位置切割。如果改为"字符种类最少的合法划分"（每个片段内字符种类尽可能少），则需要不同的策略。这类变形考验对问题本质的理解，在字符串类贪心题中属于进阶内容。
与字符串频率统计的综合应用
划分字母区间是一道把"区间合并"应用到字符串场景的题目。它告诉我们，字符串问题和区间问题之间有深刻的联系：字符串中每个字符的"活动范围"就是一个区间，字符串划分就是区间划分。
这种"字符→区间"的思维转换，在解决字符串类算法题时非常有用。很多字符串题都可以通过"预处理字符频率或位置"，然后转化为区间或数学问题来解决，从而使用成熟的区间算法框架。
划分字母区间与日志分析的工程联系
划分字母区间的算法思想在实际工程中有一个有趣的应用：日志关键词隔离分析。在系统日志中，某些关键词（如异常类型、服务名称）只应该属于某一个"事件"范围（从第一次出现到最后一次出现的日志行范围）。如果两个关键词的出现范围有重叠，说明它们属于同一个事件，应该被归入同一个日志分析单元。
这不就是划分字母区间的逻辑吗？每个关键词对应一个字母，关键词在日志中的活跃范围对应字母的区间，"把日志划分为尽可能多的独立事件段"就是划分字母区间的目标。
理解了这个工程类比，在面试中被问到"这个算法有什么实际应用"时，就有了具体生动的例子，而不是泛泛地说"字符串处理"。
三种区间处理视角的统一
回顾本篇文章涉及的三种区间处理视角：显式区间合并（解法一）、动态右边界扩展（解法二）、滑动窗口（解法三）。
三种视角从不同角度描述了同一个算法，选择哪种视角取决于交流对象。向不熟悉区间算法的人解释时，滑动窗口视角最直观（窗口扩展到包含所有字母，关闭窗口时切割）；向熟悉区间算法的人解释时，显式区间合并视角最精确（等价于 LeetCode 56 的区间合并）；写代码时，动态右边界扩展视角最简洁（只需要最后位置数组和两个指针）。
能从多个视角理解同一个算法，是算法能力成熟的标志之一。
划分字母区间是一道把贪心思想应用到字符串分割问题上的典型题，掌握了它，区间类贪心题的学习就更为完整。