Leetcode 763.划分字母区间

个人感觉很有意思的一道题~
大体思路就是,从0下标开始遍历.
确定0下标所指的字符的最远位置，如果最远位置与当前位置下标相同(即只出现一次)，则加入结果集。如果有更远的位置，从该下标的下一个位置开始遍历，依次寻找从0...maxPos中的字符的更远位置，如果存在更远的，更新maxPos.
当遍历位置与maxPos相同时，加入结果集。
本题可使用int[]数组代替HashMap以提高效率。

public List<Integer> partitionLabels(String s) {
    List<Integer> ans = new ArrayList<>();
    HashMap<Character,Integer> map = new HashMap<>();
    int len = s.length();
    for(int i = 0; i < len; i++){
        //处理第一个字符
        char c = s.charAt(i);
        //找到第一个字符的最大位置
        int maxPos = searchMaxPos(s,c,i,len);
        map.put(c,maxPos);
        //如果该字符后续未出现过
        if(maxPos == i){
            //ans中添加长度1
            ans.add(1);
            continue;
        }
        int k;
        for(k = i + 1; k < maxPos; k++){
            if(map.get(s.charAt(k)) == null){
                int temp = searchMaxPos(s,s.charAt(k),k,len);
                maxPos = Math.max(temp,maxPos);
                map.put(s.charAt(k),temp);
            }
        }
        ans.add((k-i+1));
        i = k;
    }
    return ans;
}

public int searchMaxPos(String s, char target,int index, int len){
    int maxPos = index;
    for(int i = index+1; i < len; i++) {
        if (s.charAt(i) == target) {
            maxPos = i;
        }
    }
    return maxPos;
}