力扣-904.水果成篮

题目描述

思路及实现

if-else分析法

由题我们可以知道，其实题目就是给你一个数组，然后让你找出只包含两个不同元素（数字）的最长切片长度。
那么我们可以用一个basket列表来存储当前篮子中的水果类型（也就是数字），max_num则是最多能采摘的水果数量（只包含两个不同数字的最大切片长度），cnt保存当前篮子里的水果数量（当前切片长度），mark则是用于帮助回溯前一个水果类型最前边的一颗果树的位置（比如：[3, 3, 3]，那么mark应该是1）。
然后对数组fruits进行遍历，一共四种情况，可以看代码注释。

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        max_num = 0
        cnt = 0
        basket = []
        mark = 0
        for i, num in enumerate(fruits):
            if num not in basket:  # 水果不在篮子里边
                if len(basket) < 2:  # 篮子没满
                    mark = i
                    basket.append(num)
                    cnt += 1
                else:  # 篮子满了，前一个水果和当前水果必定不同，从mark开始，构造一个新果篮的同时看下前一个果篮的值是否大于最大的果篮
                    basket = [fruits[i - 1], num]
                    if cnt > max_num:
                        max_num = cnt
                    cnt = i - mark + 1
                    mark = i
            else:  # 水果在篮子里边
                if num != fruits[i - 1]:  # 不和前一个水果相同，更新mark标记
                    mark = i
                cnt += 1
        if cnt > max_num:  # 循环结束后别忘记比较最后的果篮和最大的果篮
            max_num = cnt
        return max_num

滑动窗口

我们用left和right分别表示满足要求的窗口的左右边界，然后用哈希表来存储这个窗口内的水果（数）以及水果的数量（出现的次数）。哈希表中的Key的数量就是果篮里装的水果类型的数量，Value则是水果类型对应水果的数量。
然后每次right都会向右移动一个位置，记录并更新哈希表，并判断哈希表中是否超过两种水果（Key的数量大于2），如果超过，就要开始移动left，同时更新哈希表，如果哈希表中一个水果的数量Value为0，那就删除对应的键值对，让哈希表中只留下两种水果。

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:  # 官方题解滑动窗口
        cnt = Counter()

        left = ans = 0
        for right, x in enumerate(fruits):
            cnt[x] += 1
            while len(cnt) > 2:
                cnt[fruits[left]] -= 1
                if cnt[fruits[left]] == 0:
                    cnt.pop(fruits[left])
                left += 1
            ans = max(ans, right - left + 1)
        
        return ans

看到的优化思路：因为题目是要找最大的窗口，所以我们可以不缩小窗口，只不过不满足条件的时候不更新窗口，直接让窗口整体向右移动即可。

---

希望本文章能够帮到您~