贪心算法题解——划分字母区间【LeetCode】

763. 划分字母区间

本题目，“同一字母最多出现在一个片段中”，因为这句话，所以本质上

这道题目属于合并区间

---

一、算法逻辑（逐步思路）

✅ 目标：

将字符串 s 划分成尽可能多的片段，要求：

• 每个字母最多只出现在一个片段中；
• 所有片段拼接后仍是原始字符串；
• 返回每个片段的长度。

✅ 实现逻辑：

1. 先预处理：

• • 用字典 last 记录字符串中每个字母最后一次出现的位置；
  • 例如：s = "ababcbacadefegdehijhklij"，其中 'a' 最后出现在 8，'e' 出现在 15，等等。

1. 开始遍历划分：

• • 初始化两个指针：start 表示当前片段的起点，end 表示当前片段的最远右端；
  • 遍历字符串：

• • • 对每个字符 c，更新当前片段的 end 为 max(end, last[c])；
    • 如果当前位置 i == end，说明这个片段封闭了（它包含了所有出现在其中字符的最后位置）：

• • • • 计算这个片段的长度为 end - start + 1；
      • 把它加入答案；
      • 然后更新 start = i + 1，准备开始下一个片段。

---

二、算法核心点

✅ 核心思想：贪心策略 + 动态区间合并

• 核心贪心策略是：

• • 对于当前片段内出现的所有字母，都要等它们“最后一次出现”后，才可以结束这个片段；
  • 所以，我们用 end 表示当前片段中所有字符的最远结束点；
  • 一旦遍历指针 i 到达 end，说明这个片段所有相关字符都封闭了，可以切一刀。

• 这个过程贪心的地方在于：

• • 每次划分尽可能早地结束当前片段（在刚好满足“所有字符都只出现在一个片段”的条件下），从而得到更多的片段。

class Solution:def partitionLabels(self, s: str) -> List[int]:last = {c: i for i, c in enumerate(s)}  # 每个字母最后出现的下标ans = []start = end = 0for i, c in enumerate(s):end = max(end, last[c])  # 更新当前区间右端点的最大值if end == i:  # 当前区间合并完毕ans.append(end - start + 1)  # 区间长度加入答案start = i + 1  # 下一个区间的左端点return ans

---

三、复杂度分析

• 时间复杂度：O(n)

• • 第一次遍历构造 last：O(n)；
  • 第二次遍历划分字符串：O(n)；
  • 总共是线性时间复杂度。

• 空间复杂度：O(1)（常数级）

• • 虽然用了一个字典 last，但它最多存 26 个小写字母，属于常数空间。

---

✅ 总结表：

维度	内容
✅ 思路逻辑	利用每个字符最后出现位置，动态维护区间右边界，贪心切片
✅ 核心技巧	贪心：延迟切片直到当前片段中所有字母的最后出现位置都包含为止
✅ 时间复杂度	O(n)，两次遍历字符串
✅ 空间复杂度	O(1)，字母表大小固定，最多用 26 个键值对