滑动窗口题目：水果成篮

题目

标题和出处

标题：水果成篮

出处：904. 水果成篮

难度

5 级

题目描述

要求

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 $\text{fruits}$ 表示，其中 $\text{fruits[i]}$ 是第 $\text{i}$ 棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求收集水果：

• 你只有两个篮子，并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始收集，向右移动的过程中，你必须从每棵树（包括开始收集的树）上恰好摘一个水果。收集的水果应当符合一个篮子中的水果类型。
• 一旦你走到某棵树前，但水果不符合任何篮子中的水果类型，那么就必须停止收集。

给定一个整数数组 $\text{fruits}$，返回你可以收集的水果的最大数目。

示例

示例 1：

输入：$\text{fruits = [1,2,1]}$
输出：$\text{3}$
解释：可以收集全部 $\text{3}$ 棵树。

示例 2：

输入：$\text{fruits = [0,1,2,2]}$
输出：$\text{3}$
解释：可以收集 $\text{[1,2,2]}$ 这三棵树。
如果从第一棵树开始收集，则只能收集 $\text{[0,1]}$ 这两棵树。

示例 3：

输入：$\text{fruits = [1,2,3,2,2]}$
输出：$\text{4}$
解释：可以收集 $\text{[2,3,2,2]}$ 这四棵树。
如果从第一棵树开始收集，则只能收集 $\text{[1,2]}$ 这两棵树。

数据范围

• $\text{1}\le \text{fruits.length}\le {\text{10}}^{\text{5}}$
• $\text{0}\le \text{fruits[i]}<\text{fruits.length}$

解法

思路和算法

根据收集水果的要求，收集的水果必须是数组 $\text{fruits}$ 中的一个子数组，且子数组中至多包含 $2$ 个不同元素。由于每棵树必须摘一个水果，因此收集的水果数目等于子数组的长度。为了得到收集的水果的最大数目，应得到符合要求的最长子数组。

根据上述分析，问题转化成在数组 $\text{fruits}$ 中寻找至多包含 $2$ 个不同元素的最长子数组。

考虑数组 $\text{fruits}$ 的两个不同下标 ${\text{end}}_1$ 和 ${\text{end}}_2$，其中 ${\text{end}}_1<{\text{end}}_2$，分别以这两个下标作为结束下标，寻找至多包含 $2$ 个不同元素的最长子数组，将这两个最长子数组的开始下标分别记为 ${\text{start}}_1$ 和 ${\text{start}}_2$，则必有 ${\text{start}}_1\le {\text{start}}_2$（否则对于任意 ${\text{start}}_2\le {\text{start}}_3<{\text{start}}_1$，下标范围 $[{\text{start}}_3,{\text{end}}_1]$ 的子数组至多包含 $2$ 个不同元素，且长度大于下标范围 $[{\text{start}}_1,{\text{end}}_1]$ 的子数组）。

因此，可以使用变长滑动窗口寻找数组 $\text{fruits}$ 中的至多包含 $2$ 个不同元素的最长子数组。用 $[\text{start},\text{end}]$ 表示滑动窗口，初始时 $\text{start}=\text{end}=0$。将滑动窗口的右端点 $\text{end}$ 向右移动，移动过程中维护滑动窗口的左端点 $\text{start}$，确保滑动窗口中至多包含 $2$ 个不同元素。

使用哈希表记录滑动窗口中的每个元素的出现次数。对于每个右端点 $\text{end}$，执行如下操作。

1. 将 $\text{fruits}[\text{end}]$ 在哈希表中的次数加 $1$。

2. 如果哈希表中的元素个数大于 $2$，则将 $\text{fruits}[\text{start}]$ 在哈希表中的次数减 $1$，如果 $\text{fruits}[\text{start}]$ 在哈希表中的次数变成 $0$ 则将 $\text{fruits}[\text{start}]$ 从哈希表中删除，然后将 $\text{start}$ 向右移动一位，重复该操作直到哈希表中的元素个数小于等于 $2$。

3. 当前滑动窗口 $[\text{start},\text{end}]$ 中的子数组为至多包含 $2$ 个不同元素的子数组，其长度为 $\text{end}-\text{start}+1$，使用当前子数组的长度更新子数组的最大长度。

遍历结束之后，可以得到数组 $\text{fruits}$ 中的至多包含 $2$ 个不同元素的子数组的最大长度，即收集的水果的最大数目。

实现方面，由于数组 $\text{fruits}$ 中的所有元素都是小于数组长度的非负整数，因此可以创建一个与数组 $\text{fruits}$ 等长的数组 $\text{counts}$ 代替哈希表，当数组 $\text{counts}$ 中的一个元素值从 $0$ 变成 $1$ 时哈希表中的元素个数增加 $1$ 个，当数组 $\text{counts}$ 中的一个元素值从 $1$ 变成 $0$ 时哈希表中的元素个数减少 $1$ 个。

代码

class Solution {public int totalFruit(int[] fruits) {int length = fruits.length;int[] counts = new int[length];int maxFruits = 0;int baskets = 0;int start = 0, end = 0;while (end < length) {int type = fruits[end];counts[type]++;if (counts[type] == 1) {baskets++;}while (baskets > 2) {int prev = fruits[start];counts[prev]--;if (counts[prev] == 0) {baskets--;}start++;}maxFruits = Math.max(maxFruits, end - start + 1);end++;}return maxFruits;}
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{fruits}$ 的长度。滑动窗口的左右端点最多各遍历数组 $\text{fruits}$ 一次。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\text{fruits}$ 的长度。空间复杂度主要取决于哈希表，哈希表中的不同元素个数不超过数组 $\text{fruits}$ 的长度。