13.LeetCode 904. 水果成篮：从暴力枚举到滑动窗口的完美进阶

目录

1. 题目解析

2. 算法原理

3. 编写代码

3.1 哈希表做法

3.2 数组模拟哈希表做法（性能提升）

总结

哈喽大家好，今天我们来详细讲解 LeetCode 上的一道经典题目——904. 水果成篮。这道题本质上是一个求“最长子数组（元素种类不超过2）”的问题，非常适合用滑动窗口来解决。下面我们结合算法原理和代码实现来深入理解。

OJ链接：https://leetcode.cn/problems/fruit-into-baskets/description/

1. 题目解析

我们先来看一下题目的具体要求：

904. 水果成篮

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

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

• 你只有 两个篮子，并且每个篮子只能装 单一类型​ 的水果。每个篮子能够装的水果总量没有限制。

• 你可以选择任意一棵树开始采摘，你必须从 每棵​ 树（包括开始采摘的树）上 恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。

• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits，返回你可以收集的水果的最大数目。

示例 1：

输入：fruits = [1,2,1]

输出：3

解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]

输出：3

解释：可以采摘 [1,2,2] 这三棵树。

如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

转化思路：

将题目转化为：找出一个最长的子数组的长度，子数组中不超过两种类型的水果。

2. 算法原理

针对这道题，我们可以采用以下两种解法：

解法一：暴力枚举 + 哈希表

• 基本思路是枚举所有可能的子数组，利用哈希表统计每种子数组中水果的种类数，如果超过2种则跳过，否则更新最大长度。这种方法的时间复杂度较高，不推荐在大数据量下使用。

解法二：滑动窗口

滑动窗口是解决这类子数组问题的利器。

核心步骤：

图解示意：

• 场景1：f = [1, 2, 3, 2, 2]

  • 当右指针移动到 3时，窗口内有 [1,2,3]，种类变为3，需要收缩左边界。

• 场景2：f = [1, 2, 1, 2, 3, 2, 3, 3]

  • 同样，当遇到第三种水果 3时，我们需要移动左指针 left，直到窗口内只剩下两种水果。

3. 编写代码

根据上述算法原理，我们给出两种 Java 实现方式。

3.1 哈希表做法

这种方法思路直观，利用 HashMap来统计窗口内水果的种类和数量。

class Solution {
public int totalFruit(int[] fruits) {
//用Hash表来统计窗口内水果的种类和数量
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();

int ret = 0;//最大数目
for(int left = 0, right = 0; right < fruits.length; right++){
//入窗口
int in = fruits[right];
hash.put(in, hash.getOrDefault(in, 0) + 1);

//判断
while(hash.size() > 2){
//出窗口
int out = fruits[left];
hash.put(out, hash.get(out) – 1);

if(hash.get(out) == 0){
hash.remove(out);
}

left++;
}

//更新结果
ret = Math.max(ret, right – left + 1);
}

return ret;
}
}

注：频繁使用哈希表会导致用时较大，因为涉及到较多的哈希计算操作。

3.2 数组模拟哈希表做法（性能提升）

观察数据范围 0 <= fruits[i] < fruits.length，我们可以用数组来替代哈希表，从而大幅提升时间效率。因为数组的索引访问是 O(1)的，且没有哈希冲突的开销。

class Solution {
public int totalFruit(int[] fruits) {
//用数组模拟Hash表来统计窗口内水果的种类和数量
int n = fruits.length;
int[] hash = new int[n + 1];

int ret = 0;//最大数目
for(int left = 0, right = 0, kinds = 0; right < fruits.length; right++){
//入窗口
int in = fruits[right];
if(hash[in] == 0) kinds++;
hash[in]++;

//判断
while(kinds > 2){
//出窗口
int out = fruits[left];
hash[out]–;

if(hash[out] == 0){
kinds–;
}

left++;
}

//更新结果
ret = Math.max(ret, right – left + 1);
}

return ret;
}
}

总结

水果成篮是典型的滑动窗口模板题。我们在处理时，关键在于维护窗口内的状态（这里是水果的种类数 kinds）。当使用数组代替哈希表时，利用了题目条件对数据范围进行了优化，使得时间效率大大提升。希望大家通过这道题能熟练掌握滑动窗口的解题套路。