LeetCode刷题【763】划分字母区间

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

示例：

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

提示：

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

基本思考思路及实现

好像和官方题解想得一样，还是说下自己的思考过程吧

1. 从前面找到一个字符，往后找到他最后出现的位置，这时候想到了可能需要双指针？或者从后往前找这个字符第一次出现的位置，不过好像有点复杂，
2. 于是又想到了可以用哈希表记录下每个字符出现的最后位置，但是这时候又一个想法，是不是可以同时记下这个字符第一次出现的位置，这样就知道了这个字符需要对应的最小区间，但是如何和其他字符对应的区间是个问题，遂放弃，不过也许应该有办法
3. 那么有了前面得到的最后位置之后我们就把找当前字符最后出现位置的操作变成了O(1)复杂度
4. 继续下一个字符，判断他出现的最后位置，如果比之前那个小的话，就不用管，如果比之前那个大的话，说明这两个字符对应的最小区间需要扩大了
5. 如果找到了某个字符出现最后位置就是当前对应的区间的结束位置的话，那么说明可以形成符合题意的区间了，记录长度

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        int[] map = new int[26];
        int idx = -1;
        while (++idx < s.length()){
            map[s.charAt(idx) - 'a'] = idx;
        }
        int begin = 0;
        idx = -1;
        int lastPostion = -1;
        while (++idx < s.length()){
            lastPostion = Math.max(lastPostion,map[s.charAt(idx)-'a']);
            if (idx == lastPostion){
                list.add(idx - begin + 1);
                begin = idx+1;
            }
        }
        return list;
    }
}