Medium

题目描述

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

提示：

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

解题思路

解题思路

这道题实际上是一个滑动窗口问题的变形。题目要求我们找到包含最多两种不同水果类型的最长连续子数组。

核心思路

由于我们只有两个篮子，每个篮子只能装一种水果，所以我们需要找到最长的连续子数组，该子数组中最多包含两种不同的水果类型。

滑动窗口解法

  1. 使用双指针维护一个滑动窗口，用哈希表记录窗口内每种水果的数量
  2. 右指针不断扩展窗口，将新的水果加入窗口
  3. 当窗口内水果种类超过2种时，移动左指针缩小窗口，直到窗口内只有2种水果
  4. 在整个过程中记录窗口的最大长度

优化思路

可以进一步优化，使用哈希表只记录最多两种水果的最后出现位置，当遇到第三种水果时，移除较早出现的那种水果。

时间复杂度为 O(n)，空间复杂度为 O(1)（最多存储3种水果信息）。

代码实现

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> basket;
        int left = 0, maxFruits = 0;
        
        for (int right = 0; right < fruits.size(); right++) {
            basket[fruits[right]]++;
            
            while (basket.size() > 2) {
                basket[fruits[left]]--;
                if (basket[fruits[left]] == 0) {
                    basket.erase(fruits[left]);
                }
                left++;
            }
            
            maxFruits = max(maxFruits, right - left + 1);
        }
        
        return maxFruits;
    }
};

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        basket = {}
        left = 0
        max_fruits = 0
        
        for right in range(len(fruits)):
            basket[fruits[right]] = basket.get(fruits[right], 0) + 1
            
            while len(basket) > 2:
                basket[fruits[left]] -= 1
                if basket[fruits[left]] == 0:
                    del basket[fruits[left]]
                left += 1
            
            max_fruits = max(max_fruits, right - left + 1)
        
        return max_fruits

public class Solution {
    public int TotalFruit(int[] fruits) {
        Dictionary<int, int> basket = new Dictionary<int, int>();
        int left = 0, maxFruits = 0;
        
        for (int right = 0; right < fruits.Length; right++) {
            if (basket.ContainsKey(fruits[right])) {
                basket[fruits[right]]++;
            } else {
                basket[fruits[right]] = 1;
            }
            
            while (basket.Count > 2) {
                basket[fruits[left]]--;
                if (basket[fruits[left]] == 0) {
                    basket.Remove(fruits[left]);
                }
                left++;
            }
            
            maxFruits = Math.Max(maxFruits, right - left + 1);
        }
        
        return maxFruits;
    }
}

var totalFruit = function(fruits) {
    let left = 0;
    let maxFruits = 0;
    let basket = new Map();
    
    for (let right = 0; right < fruits.length; right++) {
        basket.set(fruits[right], (basket.get(fruits[right]) || 0) + 1);
        
        while (basket.size > 2) {
            basket.set(fruits[left], basket.get(fruits[left]) - 1);
            if (basket.get(fruits[left]) === 0) {
                basket.delete(fruits[left]);
            }
            left++;
        }
        
        maxFruits = Math.max(maxFruits, right - left + 1);
    }
    
    return maxFruits;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 每个元素最多被访问两次（一次加入窗口，一次移出窗口）
空间复杂度O(1) - 哈希表最多存储3种水果的信息，为常数空间

相关题目