力扣 划分字母区间
贪心算法，存状态，合并区间。
题目
同一字母最多出现在一个片段中，因此要找到相同字母的上界跟下界。由于是对字符串进行划分，在一个片段内，从前往后遍历，找到每个字母的最后一个下标即是可能的划分点了，同时这也是这道题贪心中所要维护的状态值。找到所有字母的最大下标后，就可以对字符串的字符再次进行比较，每次更新状态值，如果索引比状态值小，说明当前遍历过的字符还没有找完，当找到时，即可以进行划分了。划分后的区间计数后加入数组，接着移动指针到下一个数开始下一个区间的划分。
时间复杂度： O(n)，空间复杂度： O(∣Σ∣)，其中 Σ 是字符串中的字符集。
class Solution {
public List<Integer> partitionLabels(String S) {
char[] s = S.toCharArray();
int n = s.length;
int[] last = new int[26];
for (int i = 0; i < n; i++) {
last[s[i] - 'a'] = i; // 每个字母最后出现的下标
}
List<Integer> ans = new ArrayList<>();
int start = 0, end = 0;
for (int i = 0; i < n; i++) {
end = Math.max(end, last[s[i] - 'a']);
if (end == i) {
ans.add(end - start + 1);
start = i + 1;
}
}
return ans;
}
}