当前位置：首页 > ai >正文

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

ai 2025/7/13 5:51:32

763. 划分字母区间

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

这道题目属于合并区间

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

✅ 目标：

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

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

✅ 实现逻辑：

先预处理：

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

开始遍历划分：

- 初始化两个指针：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 个键值对