[滑动窗口]904. 水果成篮
904. 水果成篮
这是一个非常经典的滑动窗口（Sliding Window）算法问题，通常在面试中也会出现
🌳 题目背景（简化理解）
你来到一个农场，农场中从左到右种了一排果树，每棵树上面结了一种水果，用一个整数表示水果的类型。比如：
果树编号： 0 1 2 3 4 5
水果种类： [1, 2, 1, 3, 2, 2]这里的水果种类可以理解为水果类型的编号
比如编号1代表一种水果，编号2代表另一种水果
而不是数字2表示2种水果你想要采摘尽可能多的水果，但是有以下限制条件 👇：
📜 采摘规则（重点！）
-
你只有两个篮子 🧺🧺
- 每个篮子只能装一种类型的水果，不能混装。
- 但你可以随意选择哪两种类型的水果放入这两个篮子。
-
从任意一棵树开始采摘，但必须从当前树开始，并且每棵树都必须摘一个水果（不能跳过）。
- 一旦你开始采摘某一棵树（比如第 i 棵），你必须依次向右一棵接一棵地采摘，不能回头，也不能跳过中间的树。
-
采摘的水果必须符合你篮子中的类型
- 当前这棵树上的水果，必须是两个篮子中其中一种类型，你才能摘；
- 如果这棵树的水果类型不是你当前两个篮子中的任何一个类型，你就不能摘这棵树的水果，必须停止采摘。
-
目标：采摘尽可能多的水果 🍎🍌
- 返回你能采摘的最大水果数量（即最多能摘几棵树的水果）。
✅ 重新组织一下题目意思
给定一个数组
fruits，其中每个数字代表一棵树上的水果种类。你最多只能选择两种不同类型的水果，并且必须从某一棵树开始，从左到右连续地采摘，不能跳过任何树，但只能采摘水果种类属于你选的那两种类型。一旦遇到第三种类型的水果，就必须停止。问：从哪一段连续的树开始采摘，能摘到最多的水果？返回这个最大的数量。
其实这个问题可以转化为：
在一个数组中，找出最长的连续子数组，使得这个子数组中最多只包含两种不同的数字（即两种水果类型）。返回这个子数组的长度。
这就是经典的：“最多包含两个不同字符/数字的最长子串/子数组” 问题，通常使用 滑动窗口（Sliding Window）算法 来高效解决。
🧠 示例分析
示例 1：
输入：
fruits = [1, 2, 1]解释：
- 所有树上的水果种类是：1, 2, 1
- 你可以选择从第 0 棵树开始采摘，连续采摘 3 棵树的水果：[1, 2, 1]，其中只有两种类型：1 和 2。
- 所以最大数量是 3。
输出：
3示例 2：
输入：
fruits = [0, 1, 2, 2]解释：
- 比如你从第 1 棵树开始采摘：[1, 2, 2] → 只有两种水果类型 1 和 2，共 3 棵树，是合法的，数量为 3。
- 如果你从第 0 棵树开始：[0, 1, 2, 2]，当遇到 2（第3棵树）时已经有 0、1、2 三种类型了，不合法。所以最大只能是比如 [1,2,2] 或 [0,1] 等。
- 最长合法子数组是 [1, 2, 2]，长度为 3。
输出：
3示例 3：
输入：
fruits = [1, 2, 3, 2, 2]解释：
- 最长合法连续子数组可能是 [2, 3, 2, 2]（水果类型为 2 和 3），长度为 4。
- 如果你选 [1, 2, 3, 2, 2]，当遇到 3 时已经有三种水果类型了，不合法。
输出：
4🧩 总结题目要求
| 要求 | 说明 |
|---|---|
| 🍎 水果种类用数组表示 | fruits[i] 是第 i 棵树的水果类型（用整数表示） |
| 🧺 只能带两个篮子 | 只能收集 两种不同类型的水果 |
| 🌳 必须从某棵树开始向右连续采摘 | 不能跳过中间的树 |
| 🚫 不能遇到第三种水果类型 | 一旦遇到第 3 种类型的水果，就必须停止采摘 |
| ✅ 目标 | 找到最长的一段连续的树，其水果种类不超过两种，返回这段树的个数（即水果数量） |
🛠️ 如何解决？（算法思路）
这道题可以使用 滑动窗口（Sliding Window） 的方法高效解决：
核心思想：
维护一个窗口（即一段连续的树），窗口中最多只能有两种水果类型。如果遇到第三种类型，就调整窗口的左边界，直到窗口中又只剩下两种类型。
你可以用如下步骤：
- 使用两个指针：
left和i（或者叫right），表示窗口的左右边界。 - 使用一个哈希表（如字典）来记录当前窗口中每种水果类型以及其出现的次数。
- 遍历数组，对于每个水果：
- 将其加入窗口（加入哈希表）。
- 如果哈希表中水果种类超过 2 种：
- 移动左指针
left，缩小窗口，直到窗口中的水果种类 ≤ 2。
- 移动左指针
- 每次循环都更新最大窗口大小（即最多能采摘的水果数）。
✅ 最终答案格式
函数签名（以 Python 为例）：
def totalFruit(fruits):# 实现滑动窗口算法pass输入：fruits 是一个整数数组，表示每棵树上的水果类型。
输出：一个整数，表示你能采摘的最多水果数量（即符合要求的最长连续子数组的长度）。
🎁 总结一句话
这道题是让你在一排树中，找到最长的连续一段树，这些树上的水果种类不超过两种，返回这段树的数量。本质是求 最多包含两个不同元素的最长子数组长度，使用滑动窗口算法解决。
如果你想，我可以进一步给你提供这道题的 Python / JavaScript 实现代码，或者详细讲解滑动窗口的实现步骤！是否需要？