划分字母区间（763）

题目

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

示例

输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8]

提示

S的长度在[1, 500]之间。 S只包含小写字母 'a' 到 'z' 。

算法

遍历数组，使用Map记录每个字母出现的最后一个位置

使用贪心思想寻找最小片段：遍历数组，维护两个指针partitionStart指向片段头部、partitionEnd指向片段尾部，默认都为0；遍历的过程中，每次partitionEnd指向当前字母最后出现的位置和当前partitionEnd（即此轮遍历前的可能的片段尾部）的最大值，即值为当前片段可能的片段尾部，当i===partitionEnd时，即当前i走过的所有字母（从partitionStart开始）均在partitionStart到partitionEnd之间，此时可以将这个片段的长度放入结果数组，然后将partitionStart设置为partitionEnd的下一个位置

export const partitionLabels = (S) => {
	let map = new Map();
	const res = [];
	for (let i = 0; i < S.length; i++) {
		map.set(S[i], i);
	}
	for (let cur = 0, partitionStart = 0, partitionEnd = 0; cur < S.length; cur++) {
		partitionEnd = Math.max(map.get(S[cur]), partitionEnd);
		if (partitionEnd === cur) {
			res.push(partitionEnd - partitionStart + 1);
			partitionStart = partitionEnd + 1;
		}
	}
	return res;
};