JZX轻语：简

LeetCode 763 - 划分字母区间

发表于2024年05月02日

#双指针 #贪心

首先遍历一遍数组，得到每个字母最后出现的位置。不难得到，某个字母的最后出现位置也必定需要在同一个区间内。因此，可以使用双指针来分别指向当前元素（一个一个向右移动）、该元素所在区间的最后位置（左指针遍历到一个元素时，使用其最后一次出现位置尝试向右扩展）。如果两个指针指向同一个位置，说明该区间可以作为一个独立的结果，加入到结果数组中。

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_pos = [-1] * 26
        for i, ch in enumerate(s):
            last_pos[ord(ch) - ord('a')] = i
        left, right = 0, 0
        ans = []
        last_par_end = -1
        while left < len(s):
            right = max(right, last_pos[ord(s[left]) - ord('a')])
            if left == right:
                ans.append(right - last_par_end)
                last_par_end = right
            if right == len(s) - 1:
                break
            left += 1

        if last_par_end != len(s) - 1:
            ans.append(len(s) - 1 - last_par_end)
        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/partition-labels/