763.划分字母区间.md

方法一：贪心。

同一个字母只能出现在同一个分段内，这说明这个字母第一次出现的下标位置和最后一次出现的下标位置都应该是在一个分段内。

• 从左到右遍历扫描数组，记录每个字母最后一次出现的下标位置。

• 再次从左向右扫描数组，start、end分别作为当前分段的起始位置和结束位置。同时在过程中end始终作为扫描过程中每个字母最后一次出现下标的最大值。

• 当扫描到的位置 i 就是 end时，说明[start, end]范围内的字母不会再有出现在更后面的了，同时当前字母的最后一次出现位置是end，那么就说明后面也不会再有了（保证了范围内和边界的字母都不会在位置更后面出现的情况），这时就可以划分出一个分段。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i; // 每个z
        }
        int start = 0, end = 0;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
}