本文由旧博客内容整理迁入。原发布日期未提供，页面日期为本次整理日期。

题目

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

你想尽可能多地收集水果，但需要遵守以下规则：

  • 只有两个篮子，每个篮子只能装单一类型的水果，数量不限。
  • 可以选择任意一棵树开始采摘，必须从每棵树（包括开始采摘的树）上恰好摘一个水果。
  • 每采摘一次，向右移动到下一棵树。
  • 一旦水果不符合篮子的水果类型，就必须停止采摘。

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

示例

示例 1

1
2
输入：fruits = [1,2,1]
输出：3

解释：可以采摘全部 3 棵树。

示例 2

1
2
输入：fruits = [0,1,2,2]
输出：3

解释：可以采摘 [1,2,2]。如果从第一棵树开始，只能采摘 [0,1]。

示例 3

1
2
输入：fruits = [1,2,3,2,2]
输出：4

解释：可以采摘 [2,3,2,2]。如果从第一棵树开始，只能采摘 [1,2]。

示例 4

1
2
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5

解释：可以采摘 [1,2,1,1,2]。

解题思路

这个题也是相当简单，见题解就知道怎么做了：用哈希表记录窗口内每种水果的数量，只要种类超过两种，就收缩左端点。

C++ 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int,int>nums;
        int left=0;
        int ans=0;
        for(int i=0;i<fruits.size();i++){
            nums[fruits[i]]++;
            while(nums.size()>2){
                nums[fruits[left]]--;
                if(nums[fruits[left]]==0){
                    nums.erase(fruits[left]);
                }
                left++;
            }
            ans=max(ans,i-left+1);
        }
        return ans;
    }
};