【Check 79】2024-05-21 - 763. 划分字母区间

[larscheng]

763. 划分字母区间

[larscheng]

思路

贪心算法

• 记录每个字符最后出现的位置
• 遍历字符串，获取每个字符的最后出现位置end，此片段的结束位置即为end
• 遍历的过程中不断更新这个end值，end = max(end,当前元素的最后出现位置)
• 直到遍历到end处，start到end即为这一片段的长度，记录长度，继续遍历

代码

    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            //收集所有元素最后出现的位置
            last[s.charAt(i) - 'a'] = i;
        }
        int start = 0, end = 0;
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            //不断更新片段边界
            end = Math.max(end, last[s.charAt(i) - 'a']);
            //遍历到边界时，收集片段长度，重置开始位置
            if (i == end) {
                result.add(end - start + 1);
                start = end + 1;
            }
        }
        return result;
    }
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)