JZX轻语：简

LeetCode 904 - 水果成篮

发表于2024年05月22日

#滑动窗口 #栈

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

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

上述步骤处理完后，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

题目链接：https://leetcode.cn/problems/fruit-into-baskets/