发表于 2024.05.22

• 滑动窗口题目，其中窗口里面所涵盖的水果满足成篮要求。窗口右侧首先移向至当前满足要求的最大下标，当无法延展右侧时，左侧则滑动至窗口(刚好)只有一种水果的最小下标，再延展右侧，直至右侧移动到数组最右端。结果则来源于上述过程窗口的最大尺寸。

  在实现的过程中，我将传入的数组fruits充当为栈，并从右到左开始遍历数组，且没有显式地使用滑动窗口相关指针。使用一个集合curr_set记录当前窗口的水果种类，prev_fruit指向上一次处理的水果种类，prev_fruit_successive_cnt为prev_fruit连续采摘的次数，pickable_cnt为窗口的大小。从右往左处理水果时，如果：

  • 当前水果种类不在窗口中：根据窗口是否包含了两种水果，若是，则需要弹出非上一个水果的种类，将当前水果加入进去，并将窗口大小pickable_cnt调整为上一个水果的连续采摘次数prev_fruit_successive_cnt(本质就是移动窗口)；否则，直接容纳进窗口即可。随后，并将prev_fruit指向当前水果种类，prev_fruit_successive_cnt调整为1。

  • 当前水果种类在窗口中，且和上一个水果种类相同：直接更新连续采摘次数prev_fruit_successive_cnt。

  • 当前水果在窗口中，但不和上一个水果种类相同：将prev_fruit指向当前水果种类，prev_fruit_successive_cnt调整为1。

  上述步骤处理完后，pickable_cnt递增表示窗口延申。

  class Solution:
      def totalFruit(self, fruits: List[int]) -> int:
          # 当前窗口的水果种类
          curr_set = set()
          # 从右往左采摘
          # 上次所采摘的水果种类
          prev_fruit = -1
          # 上次该种类目前连续的次数
          prev_fruit_successive_cnt = 0
          # 目前窗口的尺寸: 当前满足要求的情况下能采摘的个数
          pickable_cnt = 0
          ans = 0
          while fruits:
              if fruits[-1] not in curr_set:  # 遇到了窗口内没有的水果种类
                  if len(curr_set) < 2:  # 窗口还能容纳该水果
                      curr_set.add(fruits[-1])
                  else:  # 不能容纳, 弹出非当前的水果
                      curr_set = {prev_fruit, fruits[-1]}
                      # 窗口内可采摘的数量调整为当前水果的连续采摘次数
                      pickable_cnt = prev_fruit_successive_cnt
  
                  # 更新当前水果
                  prev_fruit = fruits[-1]
                  prev_fruit_successive_cnt = 1
              elif fruits[-1] == prev_fruit:
                  # 同样水果, 连续次数+1
                  prev_fruit_successive_cnt += 1
              else:  # fruits[-1] in curr_set and fruits[-1] != cur_fruit
                  # 即当前水果种类也在窗口内, 但并非上一次处理水果的种类
                  prev_fruit = fruits[-1]
                  prev_fruit_successive_cnt = 1
  
              fruits.pop()  # 处理完该水果, 弹出
              # 采摘个数+1
              pickable_cnt += 1
              ans = max(ans, pickable_cnt)
          return ans

• LC 题目链接