题目描述

在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：

1. 把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
2. 移动到当前树右侧的下一棵树。如果右边没有树，就停下来。

请注意，在选择一棵树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。

你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。

用这个程序你能收集的水果总量是多少？

样例

输入：[1,2,1]
输出：3
解释：我们可以收集 [1,2,1]。

输入：[0,1,2,2]
输出：3
解释：我们可以收集 [1,2,2].
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。

输入：[1,2,3,2,2]
输出：4
解释：我们可以收集 [2,3,2,2].
如果我们从第一棵树开始，我们将只能收集到 [1, 2]。

输入：[3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：我们可以收集 [1,2,1,1,2].
如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 个水果。

注意

• 1 <= tree.length <= 40000
• 0 <= tree[i] < tree.length

算法

(双指针) $O(n)$

1. 定义指针 i 和 j，初始时 i = j = 0。记录当前区间 [i, j] 中不同种类数，以及每种水果的数量。
2. 当 i 没有到达末尾时，首先将 tree[i] 加入到记录中，如果发现种类数超过了 2，则移动 j 直到满足要求。用 j - i + 1 来更新答案。

时间复杂度

• 每个位置仅遍历两次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要用额外的数组存储当前每种水果的数量，空间复杂度为 $O(n)$；
• 可以将记录每种水果的数量改外记录当前两种水果的数量，这样空间复杂度可以到 $O(1)$，但实现起来会比较繁琐。

C++ 代码

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int n = tree.size();
        int i = 0, j = 0;
        int ans = 0;

        vector<int> types(n, 0);
        int tot_types = 0;

        while (i < n) {
            if (types[tree[i]] == 0) {
                tot_types++;
            }

            types[tree[i]]++;

            while (tot_types > 2) {
                if (types[tree[j]] == 1)
                    tot_types--;
                types[tree[j]]--;
                j++;
            }

            ans = max(ans, i - j + 1);
            i++;
        }

        return ans;

    }
};