leetcode-go/贪心算法/80-划分字母区间.md

tags, create time

tags	create time
贪心算法 双指针 字符串 哈希表 LeetCode	2026-05-16 14:30

80. 划分字母区间

题面

给你一个字符串 s 。你要把这个字符串划分为尽可能多的片段，满足：同一字母最多出现在一个片段中。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：划分结果为 "ababcbaca"、"defegde"、"hijhklij"。每个字母最多出现在一个片段中。

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

[!info] 核心约束

• 划分结果按顺序连接后必须等于原字符串（不能重排）
• 同一字母的所有出现必须落在同一个片段内
• 目标是使片段数量最大化（等价于每个片段尽量短）

---

思路

关键问题思考

先问自己一个问题：如果字母 'a' 在位置 0 和位置 7 都出现了，那第一个片段至少要覆盖到位置 7，对吗？

[!tip] 核心观察 如果字符 c 的最后出现位置是 last[c]，那么包含该字符的任意片段的右边界至少是 last[c]。

但这个条件还不够——当第一个片段被迫延伸到位置 7 时，位置 3~7 之间出现的其他字符也可能有自己的最后出现位置比 7 更远。所以片段的右边界需要被进一步"推远"。

这引出了贪心策略的核心：我们不知道第一个片段在哪里结束，但我们可以维护一个"最远能达到的位置"。

解题步骤

步骤	操作	目的
第一步	遍历字符串，记录每个字符最后一次出现的位置	知道每个字符的"活动范围"右端点
第二步	再次遍历字符串，维护当前片段的起始位置 start 和最远右边界 far	逐步推进，找到分割点
第三步	对于当前位置 i 的字符 s[i]，将 far 更新为 max(far, last[s[i]])	扩展当前片段的覆盖范围
第四步	当 i == far 时，说明当前位置就是当前片段的终点	此时可以安全切分

流程图

flowchart TD
    A[开始] --> B[第一步: 统计每个字符的最后出现位置 last]
    B --> C[初始化 start = 0, far = 0]
    C --> D{遍历字符串 i = 0 → n-1}
    D --> E["far = max(far, last[s[i]])"]
    E --> F{i == far ?}
    F -- 是 --> G[记录片段长度 far - start + 1]
    G --> H[start = far + 1]
    H --> I{i == n-1 ?}
    F -- 否 --> I
    I -- 否 --> D
    I -- 是 --> J[返回结果数组]

图解示例

以 s = "ababcbacadefegdehijhklij" 为例：

last 映射: a→8  b→5  c→7  d→14  e→15  f→11  g→13
            h→19  i→22  j→23  k→20  l→21

位置索引:   0 1 2 3 4 5 6 7 8 | 9 1011121314 | 15 16 17 18 19 20 21 22 23
          ┌─┬─┬─┬─┬─┬─┬─┬─┬─┤ ├──┼──┼──┼──┼──┼─┤  ├──┼──┼──┼──┼──┼──┼──┼──┤
字符串:    a b a b c b a c a | d  e  f  e  g  d | e  h  i  j  h  k  l  i  j

片段划分: │     片段1(长9)     │   片段2(长7)  │   片段3(长8)   │

模拟推进过程：

i=0, s[0]='a', far = max(0, last['a']=8) = 8
i=1, s[1]='b', far = max(8, last['b']=5) = 8
i=2, s[2]='a', far = max(8, 8) = 8
i=3, s[3]='b', far = max(8, 5) = 8
i=4, s[4]='c', far = max(8, last['c']=7) = 8
i=5, s[5]='b', far = max(8, 5) = 8
i=6, s[6]='a', far = max(8, 8) = 8
i=7, s[7]='c', far = max(8, 7) = 8
i=8, s[8]='a', far = max(8, 8) = 8  ← i==far，切割！记录 9

i=9, s[9]='d', far = max(9, last['d']=14) = 14
i=10,s[10]='e', far = max(14, last['e']=15) = 15
i=11,s[11]='f', far = max(15, last['f']=11) = 15
i=12,s[12]='e', far = max(15, 15) = 15
i=13,s[13]='g', far = max(15, last['g']=13) = 15
i=14,s[14]='d', far = max(15, 14) = 15
i=15,s[15]='e', far = max(15, 15) = 15  ← i==far，切割！记录 7

i=16...最终 i==far=23，切割！记录 8

正确性为什么成立？

[!question] 为什么当 i == far 时可以安全切割？

回答思路：考虑反证法。假设我们在某个位置切割后，后面还有一个片段包含了与前面片段相同的字符 —— 但我们在推进过程中已经把所有已访问字符的 last 值都纳入了 far 的计算，far 就是所有已访问字符的最后出现位置的最大值。所以 far 之后的不可能出现前面的任何字符。因此切割是安全的。

复杂度分析

指标	复杂度	说明
时间	O(n)	两次线性扫描，n 为字符串长度
空间	O(Σ)	Σ 为字符集大小（小写字母 = 26），视为常数

---

代码提示

伪代码

函数 partitionLabels(s):
    // Step 1: 建立 char -> last_position 的映射
    创建数组 last[26], 初始化为 0
    for i from 0 to s.length-1:
        last[s[i] - 'a'] = i

    // Step 2: 贪心划分
    创建空结果数组 ans
    start = 0, far = 0
    for i from 0 to s.length-1:
        far = max(far, last[s[i] - 'a'])
        if i == far:
            ans.append(i - start + 1)
            start = i + 1

    return ans

---

技巧

[!abstract] 💡 面试技巧

1. "最后一次出现"模式：这类"元素必须同组"的问题，第一步通常是找每个元素的最后出现位置。类似的题目还有 [45.跳跃游戏II](./45-跳跃游戏II.md)、[56.合并区间](./56-合并区间.md)。
2. 双指针模板：start 标记片段起点，far 标记片段终点。当到达 far 时就切一刀。这种模板在区间类问题中非常通用。
3. 不要提前切割：即使觉得当前字符在前面都没出现过，也不能轻易在这里切分——因为中间可能有别的字符把它拉得更远。far 变量就是防止过早切割的关键。

---

代码

// PartitionLabels 将字符串划分为尽可能多的片段，同一字母最多出现在一个片段中
// 参数 s: 仅由小写英文字母组成的字符串
// 返回值: 每个片段的长度列表
func partitionLabels(s string) []int {
	// 记录每个字符最后一次出现的位置
	last := [26]int{}
	for i, ch := range s {
		last[ch-'a'] = i
	}

	var ans []int
	start, far := 0, 0
	for i := range s {
		// 扩展当前片段的最远边界
		if p := last[s[i]-'a']; p > far {
			far = p
		}
		// 到达当前片段终点，切割
		if i == far {
			ans = append(ans, i-start+1)
			start = i + 1
		}
	}
	return ans
}

[!example] 简洁版写法（利用 len 预分配）

func partitionLabels(s string) []int {
	last := [26]int{}
	for i, ch := range s {
		last[ch-'a'] = i
	}

	var ans []int
	start := 0
	for i, far := 0, 0; i < len(s); i++ {
		if p := last[s[i]-'a']; p > far {
			far = p
		}
		if i == far {
			ans = append(ans, i-start+1)
			start = i + 1
		}
	}
	return ans
}