763. 划分字母区间 (opens new window)

1.区间排序

分析：开辟一个二维数组保存每个字母的起始和最远位置索引区间，接着将区间按照左边界从小到大进行排序，遍历所有出现过字母的区间：

• 如果当前区间与前面区间块存在交集，那么当前区间进行合并，更新区间块的最大右边界
• 如果当前区间左边界小于区间块最大右边界，那么当前区间不相交，记录下前一个区间块的区间长度。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[][] word=new int[26][2];

        for(int i=0;i<s.length();i++){
            int inx=s.charAt(i)-'a';
            if(word[inx][0]==0){
                word[inx][0]=i+1;
                word[inx][1]=i+1;
            }
            else{
                word[inx][1]=i+1;
            }
        }
        Arrays.sort(word,new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                if(o1[0]!=o2[0])return o1[0]-o2[0];
                else return o1[1]-o2[1];
            }
        });
        List<Integer> res=new ArrayList<>();
        int left=0,right=0;
        for(int i=0;i<word.length;i++){
            if(word[i][0]!=0){
                if(word[i][0]>right){
                    int size=right-left+1;
                    if(left!=0) res.add(size);
                    left=word[i][0];
                    right=word[i][1];
                }
                else{
                    right=Math.max(right,word[i][1]);
                }
            }
        }
        res.add(right-left+1);
        return res;
    }
}

2.贪心——区间长度

思路同55. 跳跃游戏 | Blage's Coding (blagecode.cn) (opens new window)。

仅记录每个字母出现的最后出现的索引位置。遍历整个字符串，根据每个字母的最后出现的位置来更新当前最远距离，如果当前遍历的索引 i 走到了最远距离，那么说明此时构成一个最大不相交的闭合区间。