LeetCode 904 - 水果成篮（Fruit Into Baskets）

算法刷题>LeetCode>面试经典150
6.3k words

LeetCode 904 - 水果成篮

问题描述

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

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

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

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

示例

示例 1：

1
2
3
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

1
2
3
4
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

1
2
3
4
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

1
2
3
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

约束条件

  • 1 <= fruits.length <= 10^5
  • 0 <= fruits[i] < fruits.length

解题思路

这是一个典型的滑动窗口问题。我们需要找到最长的连续子数组，其中最多包含两种不同的水果类型。

核心思想

使用滑动窗口技术：

  1. 维护一个窗口，其中最多包含两种不同的水果类型
  2. 右指针扩展窗口，添加新的水果
  3. 当出现第三种水果类型时，收缩左边界直到窗口重新满足条件
  4. 记录最大窗口大小

实现方法对比

题目提供了两种实现方式：

方法 数据结构 空间复杂度 优点 缺点
方法一 HashMap O(1) 代码简洁，只需维护实际出现的水果类型 哈希表操作有常数因子开销
方法二 哈希数组 O(n) 访问速度快，适合已知值域范围的情况 需要预分配数组空间

算法步骤

方法一：HashMap 实现

  1. 初始化：使用 HashMap 记录当前窗口中每种水果的数量
  2. 扩展窗口：右指针向右移动，将新水果加入窗口
  3. 收缩窗口：当水果种类超过 2 种时，左指针向右移动，移除水果
  4. 更新结果：记录当前窗口大小，取最大值

方法二：哈希数组实现

  1. 初始化：使用数组 window 作为哈希表，索引为水果类型，值为出现次数
  2. 扩展窗口：右指针向右移动，更新 window[fruits[right]] 计数
  3. 收缩窗口：当水果种类超过 2 种时，左指针向右移动，减少对应水果计数
  4. 更新结果：记录当前窗口大小，取最大值

实现细节

滑动窗口维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 使用 HashMap 记录当前窗口中每种水果的数量
Map<Integer, Integer> fruitCount = new HashMap<>();

// 滑动窗口的左右指针
int left = 0, right = 0;
int maxFruits = 0;

// 扩展右边界
while (right < fruits.length) {
    // 添加当前水果到窗口
    fruitCount.put(fruits[right], fruitCount.getOrDefault(fruits[right], 0) + 1);
    
    // 如果水果种类超过2种，收缩左边界
    while (fruitCount.size() > 2) {
        fruitCount.put(fruits[left], fruitCount.get(fruits[left]) - 1);
        if (fruitCount.get(fruits[left]) == 0) {
            fruitCount.remove(fruits[left]);
        }
        left++;
    }
    
    // 更新最大水果数量
    maxFruits = Math.max(maxFruits, right - left + 1);
    right++;
}

关键点分析

  1. HashMap 的作用：记录当前窗口中每种水果的数量
  2. 收缩条件：当 fruitCount.size() > 2 时需要收缩
  3. 移除水果：当某种水果数量为 0 时，从 HashMap 中完全移除
  4. 窗口大小计算：right - left + 1

代码实现

方法一：HashMap 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int totalFruit(int[] fruits) {
        // 使用 HashMap 记录当前窗口中每种水果的数量
        Map<Integer, Integer> fruitCount = new HashMap<>();
        
        int left = 0;  // 滑动窗口左边界
        int maxFruits = 0;  // 最大水果数量
        
        // 遍历数组，right 作为滑动窗口右边界
        for (int right = 0; right < fruits.length; right++) {
            // 将当前水果加入窗口
            fruitCount.put(fruits[right], fruitCount.getOrDefault(fruits[right], 0) + 1);
            
            // 如果窗口中的水果种类超过2种，需要收缩左边界
            while (fruitCount.size() > 2) {
                // 移除左边界的水果
                fruitCount.put(fruits[left], fruitCount.get(fruits[left]) - 1);
                
                // 如果某种水果数量为0，从HashMap中移除
                if (fruitCount.get(fruits[left]) == 0) {
                    fruitCount.remove(fruits[left]);
                }
                
                left++;  // 左边界右移
            }
            
            // 更新最大水果数量
            maxFruits = Math.max(maxFruits, right - left + 1);
        }
        
        return maxFruits;
    }
}

方法一详细解析

核心思想：使用 HashMap 动态维护窗口中水果的计数和种类数

关键点：

  1. HashMap 自动去重：当某种水果数量减为 0 时，从 HashMap 中移除，size() 会减少
  2. 种类数判断：通过 fruitCount.size() > 2 判断种类是否超限
  3. 逻辑清晰：代码直观，易于理解

复杂度分析：

  • 时间复杂度：O(n)，每个元素最多访问两次
  • 空间复杂度：O(1)，HashMap 最多存储 3 个键值对

方法二：哈希数组实现（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        if (n <= 2) return n; // 边界处理：数组长度≤2时直接返回
        
        int[] window = new int[n + 10]; // 哈希数组：索引为水果类型，值为出现次数
        int left = 0, maxFruits = 0, types = 0; // 窗口左指针、结果最大值、当前种类数
        
        for (int right = 0; right < n; right++) {
            // 右指针向右扩展窗口
            if (window[fruits[right]]++ == 0) {
                types++; // 遇到新种类，种类数+1
            }
            
            // 当种类超限时收缩左边界
            while (types > 2) {
                if (--window[fruits[left]] == 0) {
                    types--; // 某种水果数量归零，种类数-1
                }
                left++; // 左指针右移
            }
            
            // 更新最大窗口长度
            maxFruits = Math.max(maxFruits, right - left + 1);
        }
        return maxFruits;
    }
}

方法二详细解析

核心思想：使用数组模拟哈希表，用数组索引表示水果类型，数组值表示该水果在窗口中的出现次数

数据结构设计：

1
int[] window = new int[n + 10];
  • 索引含义：window[i] 表示水果类型 i 在当前窗口中的出现次数
  • 大小分配：根据题目约束 0 <= fruits[i] < fruits.length，分配 n + 10 的大小足够
  • 初始值：所有元素初始化为 0

关键变量：

  • types：当前窗口中水果的种类数
  • left、right：滑动窗口的左右边界
  • maxFruits：记录的最大窗口长度

核心逻辑详解：

  1. 扩展窗口：
1
2
3
if (window[fruits[right]]++ == 0) {
    types++;
}
  • 操作顺序：window[fruits[right]]++ 是后缀自增，先比较再自增
  • 判断原理：如果 window[fruits[right]] 在自增前为 0，说明这是新类型的水果，种类数加 1
  • 示例：fruits[right] = 1，如果 window[1] == 0，说明类型 1 是新类型，types++ 后种类数变为 1
  1. 收缩窗口：
1
2
3
4
5
6
while (types > 2) {
    if (--window[fruits[left]] == 0) {
        types--;
    }
    left++;
}
  • 前缀自减：--window[fruits[left]] 先自减再比较
  • 种类数管理：当某种水果数量归零时，种类数减 1
  • 窗口移动：左指针右移，缩小窗口
  1. 更新结果：
1
maxFruits = Math.max(maxFruits, right - left + 1);
  • 在每次循环中更新最大窗口长度

方法二的执行过程示例

以 fruits = [1,2,3,2,2] 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
初始状态：
window = [0, 0, 0, 0, 0] (所有类型计数为0)
left=0, right=0, types=0, maxFruits=0

right=0: fruits[0]=1
window[1]++，从0变为1，满足 window[1]==0（自增前），types++ → types=1
窗口大小=1, maxFruits=1

right=1: fruits[1]=2
window[2]++，从0变为1，满足 window[2]==0（自增前），types++ → types=2
窗口大小=2, maxFruits=2

right=2: fruits[2]=3
window[3]++，从0变为1，满足 window[3]==0（自增前），types++ → types=3
types > 2，需要收缩：
  fruits[0]=1，--window[1]，从1变为0，满足 == 0，types-- → types=2
  窗口大小=2, maxFruits=2

right=3: fruits[3]=2
window[2]++，从1变为2，不满足 window[2]==0（自增前），types不变
窗口大小=3, maxFruits=3

right=4: fruits[4]=2
window[2]++，从2变为3，不满足 window[2]==0（自增前），types不变
窗口大小=4, maxFruits=4

最终结果：4

方法二的优势

方面 优势
性能 数组访问比 HashMap 的哈希计算和冲突处理更快
内存 连续内存访问，缓存友好
代码 使用位运算思想，代码更紧凑
适用场景 适合值域已知或较小的场景

方法二的关键技巧

  1. 后置自增判断新类型：

    • if (window[x]++ == 0) 巧妙地在自增前判断是否为 0
    • 如果为 0，说明是新类型；否则是已有类型

  2. 前置自减判断类型归零：

    • if (--window[x] == 0) 在自减后判断是否为 0
    • 如果为 0，说明该类型完全移出窗口

  3. 边界处理：

    • 当 n <= 2 时直接返回，避免不必要的计算

复杂度分析：

  • 时间复杂度：O(n)，每个元素最多访问两次（右指针扩展、左指针收缩）
  • 空间复杂度：O(n)，数组大小为 n + 10，空间复杂度为 O(n)
为什么空间复杂度是 O(n)？

虽然从实用性角度看，数组是固定大小的，但从渐进复杂度分析：

  • 数组大小依赖于输入规模 n（尽管是线性的，n + 10）
  • 在分析大 O 表示法时，n + 10 ∈ O(n)
  • 当 n → ∞ 时，空间需求会增长

实际上，由于题目约束 0 <= fruits[i] < n，我们只需要 n 大小的数组即可。

复杂度分析

方法一：HashMap 实现

时间复杂度

  • O(n)：每个元素最多被访问两次（一次被右指针添加，一次被左指针移除）
  • 虽然内层有 while 循环，但每个元素最多被处理一次

空间复杂度

  • O(1)：HashMap 最多存储 3 个键值对（2种水果类型 + 1种新类型）
  • 空间复杂度与输入规模无关

方法二：哈希数组实现

时间复杂度

  • O(n)：每个元素最多被访问两次
  • 右指针遍历整个数组，左指针最多遍历一次

空间复杂度

  • O(n)：需要 n + 10 大小的数组用于哈希映射
  • 取决于输入规模，但数组大小是线性的

方法比较总结

方面 方法一 (HashMap) 方法二 (哈希数组)
时间复杂度 O(n) O(n)
空间复杂度 O(1) O(n)
代码简洁度 ★★★★☆ ★★★☆☆
执行效率 较慢（哈希运算） 更快（直接索引）
内存占用 较少（只存实际出现的类型） 较多（预分配数组）
适用场景 通用场景 值域较小且已知
推荐度 ★★★☆☆ ★★★★★

总结：如果值域范围较小（如本题），哈希数组方法在性能和代码清晰度上都有优势。如果值域很大或未知，HashMap 方法更灵活。

关键收获

  1. 滑动窗口模板：这是滑动窗口问题的经典应用
  2. 数据结构选择：HashMap vs 哈希数组，根据场景选择
  3. 边界处理：正确处理窗口收缩的条件
  4. 时间复杂度优化：通过滑动窗口避免暴力解法的时间复杂度
  5. 自增自减技巧：使用 a++ == 0 和 --a == 0 简化代码逻辑

常见陷阱

  1. 忘记移除元素：当窗口收缩时，必须正确移除左边界元素
  2. HashMap 清理：当元素数量为 0 时，要从 HashMap 中完全移除
  3. 窗口大小计算：使用 right - left + 1 计算当前窗口大小
  4. 种类数管理：正确跟踪窗口中的种类数，确保逻辑一致
  5. 数组大小：使用哈希数组时，确保数组大小足够容纳所有可能的值

相关问题

总结

这道题是滑动窗口算法的经典应用，题目要求我们找到最多包含两种不同元素的最长连续子数组。

核心要点

  1. 滑动窗口思想：使用双指针维护一个满足条件的窗口
  2. 两种实现方式：
    • HashMap：适用于通用场景，空间复杂度 O(1)
    • 哈希数组：适用于值域较小的情况，执行效率更高
  3. 关键技巧：
    • 使用 types 变量跟踪窗口中的种类数
    • 利用自增自减运算符简化判断逻辑
    • 正确处理窗口的扩展和收缩

学习价值

这道题不仅考查滑动窗口的基本应用，还展示了在不同数据结构选择上的权衡。理解这两种实现方式有助于：

  • 掌握滑动窗口算法的核心思想
  • 学会根据场景选择合适的数据结构
  • 熟悉 Java 中自增自减运算符的妙用
  • 提升代码优化的意识

通过这道题，我们可以深刻理解滑动窗口算法在实际问题中的应用，并为解决类似的子数组/子串问题打下坚实基础。