划分字母区间如何用贪心求解？（LeetCode 763）

简化版

给一个字符串 s，要把它划分成尽可能多的片段，使得同一个字母只出现在一个片段里，返回每个片段的长度。贪心策略：先记录每个字母最后一次出现的下标；然后遍历字符串，维护当前片段的右边界 end（= 片段内所有字母的「最后出现位置」的最大值），当遍历下标 i 走到 end 时，说明这个片段里的所有字母都已闭合，切一刀。

详细版

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;
}

预处理 last[]：先扫一遍，记下每个字母最后出现的位置。这是划分的依据。
动态右界 end：遍历时把当前片段的结束位置不断扩展为「已见字母中最靠后的 last」。
切割时机：i == end 时当前片段的所有字母都不会再出现在后面，安全切段。
复杂度：O(n) 时间、O(26) 空间。

完整版教学

一、划分的约束：同字母不能跨段

要求「同一字母只在一个片段」。这意味着：如果字母 c 出现在某片段里，那么 c 的所有出现（尤其是最后一次）都必须被包进同一个片段。 所以一个片段的右边界，至少要延伸到「片段内已出现的每个字母的最后一次出现位置」的最远处。这就是解题的钥匙——每个字母的 last 位置。

二、第一步：预处理每个字母的最后位置

先遍历一遍字符串，用 last[26] 记录每个字母最后一次出现的下标。因为只有 26 个小写字母，这一步 O(n) 时间、O(26) 空间。有了 last，我们就能在划分时随时知道「当前片段必须至少延伸到哪里」。

三、第二步：贪心扩展右边界

从左遍历，维护当前片段的起点 start 和动态右界 end：

每遇到一个字母 c，就把 end 更新为 max(end, last[c])——因为 c 必须待在本段，本段就得延伸到 c 最后出现处。
随着遍历，end 会被段内各字母的 last 不断往右撑。

切割条件是 i == end：当遍历下标 i 恰好追上当前右界 end 时，意味着——从 start 到 i 这段里，所有出现过的字母的最后位置都 ≤ i，即它们全部在这段内闭合，后面再不会出现。这时可以安全地切一刀：片段 [start, i] 满足约束，记录长度 end - start + 1，然后 start 移到 i+1 开启下一段。

四、为什么这样切「片段数最多」

贪心目标是「尽可能多的片段」。这个算法在每个能切的位置都立刻切（i==end 就切），一刻也不多留——这自然得到最多的片段数。

正确性：i == end 是「当前片段能结束的最早位置」。为什么最早？因为在此之前，总存在某个已见字母的 last 位置 > i（否则更早就 i==end 了），那个字母还没闭合，此刻切会让它跨段，违反约束。所以不到 i==end 不能切，一到 i==end 就该切——每段都取最短合法长度，片段数就最多。

五、举例走一遍

s = "ababcbacadefegdehijhklij"：

预处理后 last['a']=8, last['b']=5, last['c']=7, last['d']=14, last['e']=15, ...
i=0 ‘a’：end=8。i=1 ‘b’：end=max(8,5)=8… 一直到 i=8 ‘a’，此时 i==end==8，切第一段 [0,8]，长度 9。
接着从 9 开始，‘d’ 把 end 撑到 14、‘e’ 撑到 15…直到 i=15，切第二段，长度 7。
再切出第三段长度 8。结果 [9,7,8]。

每当扫描到片段内新字符，都要用它的最后位置继续扩张 end，形成“连锁覆盖”。只有 i 追上动态 end 时，当前片段中所有字符的最后出现都已被包住，此处才是最早合法切点。

六、贪心选择为什么不会堵死未来

本题每一步选择是：预处理每字符最后位置，扫描片段时将 end 扩为片段内所有字符最后位置的最大值；i==end 时立即切分。

正确性不能只靠直觉，核心证明是：end 之前任何位置切都会把某字符留到后段；到 end 时当前段字符均不会再出现，最早切能最大化段数。这说明任意最优方案都能调整为包含当前贪心选择的方案，且目标值不会变差。

排序或预处理，建立可比较的选择顺序
维护“当前选择给未来留下的有效边界”
若候选不劣于现有边界，则提交选择并更新状态

数字推演：ababcbacadefegdehijhklij 第一段扫描 a/b/c 后 end=8，于下标8切出长度9。

记忆钩子：贪心不是“选眼前最大”，而是选一个能被交换论证证明、对未来最宽松的代表。

七、退化边界、复杂度与反例检查

实现边界是：字符集不固定时用 Map；end 动态扩张不能只看片段首字符；输出长度时记录 start。

检查项	必须回答
排序键	为什么按这个维度和方向排序
局部选择	它保留了什么未来可能性
正确性	交换、领先或反证中的哪一种
失败边界	哪个题目条件一改就不能贪心
复杂度	排序成本与扫描成本是否都计入

测试时至少覆盖单元素、全部相等、严格递增/递减、恰好卡在边界、局部最优容易误导的反例。若无法写出交换论证或领先性质，应暂停使用贪心，转而尝试动态规划、搜索或数据结构。

例如扫描 abac 时，读到首个 a 得 end=2，随后 b 把 end 保持在2；只有到下标2才能切。若在下标1提前切，后面的 a 会跨越两个片段，直接违反约束。

八、常见误区与追问

误区：只看当前字符最后位置即可切。 片段内早先字符可能把 end 扩得更远。
误区：应尽量晚切以获得更多段。 满足约束的最早位置切才给后续最多机会。
误区：排序字符后更容易处理。 排序会破坏原连续片段。
追问：为什么 i==end 安全？ 当前片段出现过的所有字符最后位置都不超过 end。
追问：为何片段数最多？ 任何合法第一刀都不能早于该 end。
追问：Unicode 字符怎么办？ 用字符到最后下标的映射，并明确码点遍历。

九、加强记忆

划分字母区间 = 贪心扩展右边界。约束「同字母不跨段」⇒ 片段必须包住段内每个字母的最后出现位置。两步：① 预处理 last[26] 记每个字母最后下标；② 遍历时 end = max(end, last[当前字母]) 动态撑大片段右界，当 i == end（当前所有字母都闭合的最早位置）就切一刀并记长度 end-start+1。每次在最早合法处切，故片段数最多。O(n) 时间 O(26) 空间。核心一句：片段的终点，是段内所有字母最后位置的最大值。

简化版

详细版