904. 水果成篮

我不是女神ヾ 2024-04-03 13:37 113阅读 0赞

问题描述：

> 你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 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\] 这五棵树。

思路：其实这个问题反复看了很多遍才看懂，其实就是篮子里只能装两个不同的整数，不能间断只能连续装数的前提下，最多可以装多少两个不同的整数。

第一时间就想到的是滑动窗口算法，

![在这里插入图片描述][a2fbc21d7cf64409a70708854f1565b5.jpeg_pic_center]  
用map来保存窗口内的整数及整数的个数，保证map的键值对最多只有2个。  
count保存当前窗口的整数个数  
max保存窗口的最大整数个数  
所以只会出现以下几种情况：

1. right右移，将整数放入map，对应的value++，count++
     2. 若map.size>2,即窗口中整数超过2个了，就一直移动左指针，map中对应value--，count--，若value=0，则删除该键值对。
     3. max = {
        max,count}两者中的较大值

那么直接写代码：

class Solution {
        
         public int totalFruit(int[] fruits) {
        
    
            // 滑动窗口，左右指针
            int left=0,right=0;
    
            // 最多的水果采摘数
            int max=0;
    
            int count=0;
    
            // map
            Map<Integer,Integer> map = new HashMap<>();
    
            for (right = 0;  right < fruits.length ; right++) {
        
                // 加入map,若该key已存在，value++,如果该key不存在，则赋1
                map.put(fruits[right],map.getOrDefault(fruits[right],0)+1);
                count++;
    
                // 判断map的键值对是否超过2
                while(map.size() > 2){
        
                    // 若大于2，则移动左指针,并从map中更新该键值对，直到某键值对的value减少为0后剔除
                    map.computeIfPresent(fruits[left],(k,v)-> --v);
                    count--;
                    if(map.get(fruits[left]) == 0){
        
                        map.remove(fruits[left]);
                    }
                    left++;
                }
                max = Math.max(count,max);
            }
            return max;
        }
    }

总结：经典的滑动窗口模型，左右指针作为边界，动态滑动。

[a2fbc21d7cf64409a70708854f1565b5.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/09c2ef0ea00f45f5b62e3157a75a1464.jpeg