发表于 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 题目链接