LeetCode 763 - 划分字母区间（Partition Labels）

问题描述

给你一个字符串 s，要求将这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例 1:

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

示例 2:

1
2
3

输入：s = "eccbbbbdec"
输出：[10]
解释：整个字符串只能构成一个片段。

约束条件:

1 <= s.length <= 500
s 仅由小写英文字母组成

解题思路

这道题目的关键是理解"同一字母最多出现在一个片段中"的约束条件。这意味着，如果一个片段包含了某个字母，那么这个字符串中所有相同的字母都必须包含在这个片段中。

基于这个要求，我们可以使用贪心算法：

首先，我们需要知道每个字符在字符串中最后出现的位置
然后，我们从头遍历字符串，对于每个字符，其最后出现的位置就是当前片段的潜在结束位置
随着遍历过程，我们不断更新当前片段的结束位置（取最远的那个）
当我们遍历到当前片段的结束位置时，就找到了一个符合条件的片段

这个算法的核心思想是：要让同一字母都在一个片段中，那么片段的结束位置必须至少延伸到这个字母最后出现的位置。

代码实现

func partitionLabels(s string) []int {
	// 记录每个字母最后出现的位置
	lastPosition := make([]int, 26)
	for i, char := range s {
		lastPosition[char-'a'] = i
	}

	var result []int
	start, end := 0, 0

	// 遍历字符串，不断更新当前区间的结束位置
	for i, char := range s {
		// 更新当前区间的结束位置（取最远的位置）
		charLastPos := lastPosition[char-'a']
		if charLastPos > end {
			end = charLastPos
		}

		// 如果当前位置达到了区间的结束位置，说明找到了一个分区
		if i == end {
			// 添加区间长度
			result = append(result, end-start+1)
			// 更新下一个区间的开始位置
			start = end + 1
		}
	}

	return result
}

实现细节

代码实现可以分为两个主要部分：

1. 预处理：记录每个字母最后出现的位置

首先，我们创建一个长度为 26 的数组（假设字符串只包含小写字母），用于记录每个字母在字符串中最后出现的位置。

lastPosition := make([]int, 26)
for i, char := range s {
    lastPosition[char-'a'] = i
}

2. 贪心划分：找到符合条件的片段

然后，我们再次遍历字符串，维护当前片段的开始位置 start 和结束位置 end。

对于每个字符，我们查看它最后出现的位置，如果这个位置比当前的 end 更远，就需要更新 end：

charLastPos := lastPosition[char-'a']
if charLastPos > end {
    end = charLastPos
}

当我们遍历到位置 i 等于当前维护的 end 时，意味着从 start 到 end 的这个片段满足条件（所有字母都只出现在这个片段中）。此时，我们将这个片段的长度添加到结果中，并更新下一个片段的开始位置：

if i == end {
    result = append(result, end-start+1)
    start = end + 1
}

方法比较

方面	贪心算法	其他可能的方法（如分治）
时间复杂度	O(n)	O(n²) 或更高
空间复杂度	O(1) (只需固定大小数组)	可能需要更多空间
优点	简单直观，效率高	适应性可能更强
缺点	针对特定问题	实现复杂，效率较低
推荐度	★★★★★	★★☆☆☆

复杂度分析

时间复杂度：$O(n)$，其中 n 是字符串的长度。我们需要两次遍历字符串，第一次记录每个字母最后出现的位置，第二次进行分区。
空间复杂度：$O(1)$，因为我们只需要一个固定大小的数组来记录字母的最后出现位置（最多 26 个字母）。

关键收获

贪心算法思想：这道题是贪心算法的典型应用，通过每次选择局部最优解（尽可能小的满足条件的片段），最终达到全局最优（最多的片段数量）。
预处理技巧：提前记录每个字母最后出现的位置，避免了重复查找，提高了算法效率。
双指针：利用 start 和 end 两个指针来维护当前片段的范围，是一种常见且有效的技巧。
问题转化：将"同一字母最多出现在一个片段中"转化为"找到一个最小的包含所有出现字母的区间"，是解决此类问题的关键。

这道题目体现了贪心算法的精髓：通过每次做出局部最优的选择，最终得到全局最优解。理解这种思想对解决其他类似的区间划分问题也有很大帮助。