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

---
tags: [贪心算法, 双指针, 字符串, 哈希表, LeetCode]
create time: 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 时，说明当前位置就是当前片段的终点 | 此时可以安全切分 |

### 流程图

```mermaid
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 变量就是防止过早切割的关键。

---

## 代码

```go
// 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 预分配）
>
> ```go
> 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
> }
> ```