【力扣】763. 划分字母区间

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

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

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

示例 1：

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

示例 2：

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

提示：

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

题解：

贪心算法：

func partitionLabels(s string) []int {
	hash := make(map[int]int, 26)
	// 获取每个字符的最远距离
	for i, char := range s {
		hash[int(char-'a')] = i
	}
	var result []int
	var left, right int
	for i, char := range s {
		// 获取右边界
		right = max(right, hash[int(char-'a')])
		// 到达右边界则开始收集结果并为下一次循环准备左边界
		if i == right {
			result = append(result, right-left+1)
			left = i + 1
		}
	}
	return result
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}