LeetCode_滑动窗口_中等_904.水果成篮

﹏ヽ暗。殇╰゛Y 2023-10-07 20:24 9阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

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

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

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

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

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

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

**提示：**  
1 <= fruits.length <= 105  
0 <= fruits\[i\] < fruits.length

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/fruit-into-baskets

## 2.思路 ##

（1）滑动窗口 & 哈希表  
① 定义滑动窗口的左右指针 left 和 right，其初始值均为 0；  
② 定义 hashMap ，用于记录滑动窗口中不同水果的种类以及对应出现的数目；  
③ 遍历数组 fruits：  
1）记当前水果种类为 type = fruits\[right\]，增大窗口后并将当前水果加入到窗口中；  
2）由于**最多只能采摘两种类型的水果**，所以我们需要**保证窗口中的水果种类数不超过 2**；  
3）之后再用 res 来保存遍历时窗口中水果的最大数目，也即 hashMap 中所有 value 之和的最大值。  
④ 遍历结束后，返回 res 即可。

## 3.代码实现（Java） ##

//思路1————滑动窗口 & 哈希表
    class Solution {
        
        public int totalFruit(int[] fruits) {
        
            int res = 0;
            int length = fruits.length;
            //滑动窗口的左右指针
            int left = 0, right = 0;
            // hashMap 记录滑动窗口中不同水果的种类以及对应出现的数目
            Map<Integer, Integer> hashMap = new HashMap<>();
            while (right < length) {
        
                //当前水果种类
                int type = fruits[right];
                //增大窗口
                right++;
                //将当前水果加入到窗口中
                hashMap.put(type, hashMap.getOrDefault(type, 0) + 1);
                //保证窗口中的水果种类数不超过 2
                while (hashMap.size() > 2) {
        
                    int removedType = fruits[left];
                    left++;
                    if (hashMap.get(removedType) == 1) {
        
                        hashMap.remove(removedType);
                    } else {
        
                        hashMap.put(removedType, hashMap.get(removedType) - 1);
                    }
                }
                //计算窗口中的水果数目，并更新 res
                int curNum = 0;
                for (Integer val : hashMap.values()) {
        
                    curNum += val;
                }
                res = Math.max(res, curNum);
            }
            return res;
        }
    }
    
    /*
    	参考本题官方题解，上面的代码还有可以优化的地方：
    	在更新 res 时，可以使用窗口左右指针之间的距离来表示窗口中的水果数目，这样避免了多次计算 hashMap 中所有 value 之和
    */
    class Solution {
        
        public static int totalFruit(int[] fruits) {
        
            int res = 0;
            int length = fruits.length;
            Map<Integer, Integer> hashMap = new HashMap<>();
            //窗口的左右指针
            int left = 0, right = 0;
            while (right < length) {
        
                //当前水果种类
                int type = fruits[right];
                hashMap.put(type, hashMap.getOrDefault(type, 0) + 1);
                //保证窗口中的水果种类数不超过 2
                while (hashMap.size() > 2) {
        
                    int removedType = fruits[left];
                    hashMap.put(removedType, hashMap.get(removedType) - 1);
                    if (hashMap.get(removedType) == 0) {
        
                        hashMap.remove(removedType);
                    }
                    //缩小窗口
                    left++;
                }
                //更新 res
                res = Math.max(res, right - left + 1);
                //增大窗口
                right++;
            }
            return res;
        }
    }