算法题 水果成篮

水果成篮

问题描述

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

你有两个篮子，每个篮子只能装单一类型的水果，但你可以选择任意两棵树开始收集水果。

你必须从每棵树（包括选择的起始树）连续地收集水果，一旦遇到第三种类型的水果，就必须停止。

返回你能收集的水果的最大数目。

示例：

输入:fruits=[1,2,1]输出:3解释:可以收集[1,2,1]输入:fruits=[0,1,2,2]输出:3解释:可以收集[1,2,2]输入:fruits=[1,2,3,2,2]输出:4解释:可以收集[2,3,2,2]输入:fruits=[3,3,3,1,2,1,1,2,3,3,4]输出:5解释:可以收集[1,2,1,1,2]

算法思路

滑动窗口 + 哈希表：

1. 问题转化：

   • 找到最长的连续子数组，其中最多包含两种不同的元素
   • 这是一个经典的滑动窗口问题

2. 滑动窗口策略：

   • 右指针right：扩展窗口，将新水果加入篮子
   • 左指针left：当篮子中水果种类超过2种时，收缩窗口
   • 哈希表：记录当前窗口中每种水果的出现次数

3. 窗口收缩条件：

   • 当哈希表的大小 > 2 时，需要收缩左边界
   • 移除fruits[left]，如果其计数变为0，从哈希表中删除
   • left++继续收缩，直到哈希表大小 ≤ 2

4. 最大长度更新：

   • 每次扩展右边界后，如果窗口有效（水果种类 ≤ 2），更新最大长度
   • 最大长度 =right - left + 1

代码实现

方法一：滑动窗口 + 哈希表

importjava.util.*;classSolution{/** * 水果成篮 - 滑动窗口 * * @param fruits 水果类型数组 * @return 能收集的最大水果数目 * * 算法思路： * 1. 使用滑动窗口维护最多包含2种水果的连续子数组 * 2. 哈希表记录当前窗口中每种水果的计数 * 3. 当水果种类超过2种时，收缩左边界 */publicinttotalFruit(int[]fruits){Map<Integer,Integer>fruitCount=newHashMap<>();intleft=0;intmaxFruits=0;// 右指针扩展窗口for(intright=0;right<fruits.length;right++){// 将当前水果加入窗口fruitCount.put(fruits[right],fruitCount.getOrDefault(fruits[right],0)+1);// 当水果种类超过2种时，收缩左边界while(fruitCount.size()>2){intleftFruit=fruits[left];fruitCount.put(leftFruit,fruitCount.get(leftFruit)-1);// 如果某种水果计数为0，从哈希表中移除if(fruitCount.get(leftFruit)==0){fruitCount.remove(leftFruit);}left++;}// 更新最大水果数目maxFruits=Math.max(maxFruits,right-left+1);}returnmaxFruits;}}

算法分析

• 时间复杂度：O(n)

  • 每个元素最多被访问两次（右指针和左指针各一次）
  • 哈希表操作为 O(1)

• 空间复杂度：O(1)

  • 哈希表最多存储3个键值对（收缩前）

算法过程

1：fruits = [1,2,1]

滑动窗口过程：

初始: left=0, maxFruits=0, fruitCount={} right=0: fruits[0]=1 - fruitCount={1:1} - maxFruits = max(0, 0-0+1) = 1 right=1: fruits[1]=2 - fruitCount={1:1, 2:1} - maxFruits = max(1, 1-0+1) = 2 right=2: fruits[2]=1 - fruitCount={1:2, 2:1} - maxFruits = max(2, 2-0+1) = 3 返回 3

2：fruits = [3,3,3,1,2,1,1,2,3,3,4]

窗口扩展到 [3,3,3,1] → 种类=2，长度=4 继续扩展到 [3,3,3,1,2] → 种类=3，需要收缩 收缩过程： - 移除fruits[0]=3 → {3:2, 1:1, 2:1} - 移除fruits[1]=3 → {3:1, 1:1, 2:1} - 移除fruits[2]=3 → {1:1, 2:1}，left=3 窗口变为 [1,2]，继续扩展... 最终找到 [1,2,1,1,2]，长度=5

3：fruits = [1,2,3,2,2]

[1] → len=1 [1,2] → len=2 [1,2,3] → 种类=3，收缩到 [2,3] → len=2 [2,3,2] → len=3 [2,3,2,2] → len=4 最大长度=4

测试用例

importjava.util.*;publicclassTest{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[]fruits1={1,2,1};System.out.println("Test 1: "+solution.totalFruit(fruits1));// 3// 测试用例2：需要收缩窗口int[]fruits2={0,1,2,2};System.out.println("Test 2: "+solution.totalFruit(fruits2));// 3// 测试用例3：中间有最长序列int[]fruits3={1,2,3,2,2};System.out.println("Test 3: "+solution.totalFruit(fruits3));// 4// 测试用例4：复杂情况int[]fruits4={3,3,3,1,2,1,1,2,3,3,4};System.out.println("Test 4: "+solution.totalFruit(fruits4));// 5// 测试用例5：所有相同int[]fruits5={1,1,1,1,1};System.out.println("Test 5: "+solution.totalFruit(fruits5));// 5// 测试用例6：两种交替int[]fruits6={1,2,1,2,1,2};System.out.println("Test 6: "+solution.totalFruit(fruits6));// 6// 测试用例7：单个元素int[]fruits7={1};System.out.println("Test 7: "+solution.totalFruit(fruits7));// 1// 测试用例8：两个元素int[]fruits8={1,2};System.out.println("Test 8: "+solution.totalFruit(fruits8));// 2// 测试用例9：三种连续int[]fruits9={1,2,3};System.out.println("Test 9: "+solution.totalFruit(fruits9));// 2// 测试用例10：大数组int[]fruits10=newint[40000];Arrays.fill(fruits10,1);fruits10[20000]=2;fruits10[30000]=3;System.out.println("Test 10: "+solution.totalFruit(fruits10));// 20001// 测试用例11：边界值int[]fruits11={0,1,0,1,0,1,0,1,0,1,2};System.out.println("Test 11: "+solution.totalFruit(fruits11));// 10// 测试用例12：从后往前的最长序列int[]fruits12={1,2,1,1,2,2,2,2,2};System.out.println("Test 12: "+solution.totalFruit(fruits12));// 9}}

关键点

1. 滑动窗口：

   • 右指针不断扩展，左指针在必要时收缩
   • 保证窗口内最多包含2种水果

2. 哈希表：

   • 记录当前窗口中每种水果的数量
   • 通过大小判断是否超过2种
   • 通过计数为0时移除键来准确维护种类数

3. 边界条件处理：

   • 数组长度 ≤ 2 时直接返回长度
   • 空数组

常见问题

1. 为什么不用Set而用Map？

   • Set只能记录种类，无法记录每种水果的数量
   • 需要知道何时可以安全移除某种水果（计数为0时）

2. 如果篮子数量不是2而是k？

   • 算法逻辑相同，只需要将条件> 2改为> k
   • 这是滑动窗口解决"最多k种元素"问题的通用模式