Leetcode763 Partition Labels

给定一个仅包含小写字母的字符串，问分隔为尽可能多的部分，使得每一个字母仅仅出现在一个部分中，返回分隔的各个部分的长度

对于每个出现的字母，都有最早出现和最晚出现（如果仅出现一次则最早就是最晚）的下标，那么包含这个字母的部分最短最短也要是最早下标到最晚出现下标这一段。然而对每个字母都是如此，所以我们只能取最晚最晚的那个下标才能分隔。

举个栗子，比如第一个字母是a，最早出现下标是0，最晚是6，那么这一段最短就是[0-6]，长度为7，但是在下标1到下标5会出现其他的字母，比如下标1对应字母b，他最晚出现的下标是12，那么这一段最短就变为了[0-12]，长度为13了，同理在“沿途”中还有可能会继续更新这个最晚下标，导致这一部分长度变长，直到再也没有字母的最晚出现下标比当前这段所记录的最晚下标还远，则表示这段可以分隔了。

如此往复

本题代码

public static List<Integer> partitionLabels(String S) {
    int[] lastPosition = new int[26];
    for (int i=0; i<S.length(); ++i) {
        lastPosition[S.charAt(i) - 'a'] = i;
    }
    List<Integer> ans = new ArrayList<>();
    int curLast = 0;    // 目前最远的
    int pos = 0;    // 因为答案是每一段的长度, 所以设置pos记录每一段的头下标
    for (int i=0; i<S.length(); ++i) {
        // 还有更远的，则更新
        curLast = Math.max(curLast, lastPosition[S.charAt(i) - 'a']);
        // 没有更远的了，分隔
        if (i == curLast) {
            ans.add(i - pos + 1);
            pos = i + 1;
        }
    }
    return ans;
}