【不定长滑动窗口】【灵神题单】【刷题笔记】

采摘水果

• fruits[i]表示第i棵树上的水果种类
• 目的是尽可能多收集水果
• 规矩:
  • 只有两个篮子，且每个篮子只能装一种水果，但是每个篮子能装的总量没限制
  • 一旦开始采摘，就会连续采摘，把两个篮子都用掉
  • 也就是说，采摘到最后一颗，或者遇到第三种水果，没有篮子装了就停止！

class Solution:def totalFruit(self, fruits: List[int]) -> int:n = len(fruits)left = 0res = 0cnt = {}for right in range(n):# 进入窗口,记录到字典中，出现了什么水果，以及采摘了几次if fruits[right] in cnt:cnt[fruits[right]] += 1else:cnt[fruits[right]] = 1# while len(cnt) > 2:cnt[fruits[left]] -= 1if cnt[fruits[left]] == 0:del cnt[fruits[left]]left += 1res = max(res, right - left + 1)return res