划分字母区间

原题链接

使用的方法

• 贪心算法

解题思路

首先记录每个字符最后出现的位置，然后从左到右遍历字符串，维护一个当前片段的结束位置，
当遍历到当前位置时，如果当前位置等于当前片段的结束位置，则将当前片段加入结果中，并更新下一个片段的开始位置。

代码实现

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList();

        // 1. 记录每个字符最后出现的索引
        int[] last = new int[26];
        for(int i = 0; i < s.length(); i++){
            last[s.charAt(i) - 'a'] = i;
        }

        int start = 0 , end = 0;

        // 2. 遍历字符串
        for(int i = 0; i < s.length(); i++){
            // 更新当前片段的边界，取最大值
            end = Math.max(end,last[s.charAt(i) - 'a']);
            // 3. 如当前位置就是当前片段的结束位置，切分
            if(i == end){
                res.add(end - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
}