In a row of trees, the `i`-th tree produces fruit with type `tree[i]`.

You start at any tree of your choice, then repeatedly perform the following steps:

2. Move to the next tree to the right of the current tree.  If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Example 1:

``````Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].
``````

Example 2:

``````Input: [0,1,2,2]
Output: 3 Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].
``````

Example 3:

``````Input: [1,2,3,2,2]
Output: 4 Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].
``````

Example 4:

``````Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5  Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.
``````

Note:

1. `1 <= tree.length <= 40000`

2. `0 <= tree[i] < tree.length`

这道题说是给了我们一排树，每棵树产的水果种类是 tree[i]，说是现在有两种操作，第一种是将当前树的水果加入果篮中，若不能加则停止；第二种是移动到下一个树，若没有下一棵树，则停止。现在我们有两个果篮，可以从任意一个树的位置开始，但是必须按顺序执行操作一和二，问我们最多能收集多少个水果。说实话这道题的题目描述确实不太清晰，博主看了很多遍才明白意思，论坛上也有很多吐槽的帖子，但实际上这道题的本质就是从任意位置开始，若最多只能收集两种水果，问最多能收集多少个水果。那么再进一步提取，其实就是最多有两个不同字符的最长子串的长度，跟之前那道 Longest Substring with At Most Two Distinct Characters 一模一样，只不过换了一个背景，代码基本都可以直接使用的，博主感觉这样出题有点不太好吧，完全重复了。之前那题的四种解法这里完全都可以使用，先来看第一种，使用一个 HashMap 来记录每个水果出现次数，当 HashMap 中当映射数量超过两个的时候，我们需要删掉一个映射，做法是滑动窗口的左边界 start 的水果映射值减1，若此时减到0了，则删除这个映射，否则左边界右移一位。当映射数量回到两个的时候，用当前窗口的大小来更新结果 res 即可，参见代码如下：
解法一：

class Solution {
public:
int totalFruit(vector& tree) {

``````   int res = 0, start = 0, n = tree.size();
unordered_map<int, int> fruitCnt;
for (int i = 0; i < n; ++i) {
++fruitCnt[tree[i]];
while (fruitCnt.size() > 2) {
if (--fruitCnt[tree[start]] == 0) {
fruitCnt.erase(tree[start]);
}
++start;
}
res = max(res, i - start + 1);
}
return res;
``````

}
};

我们除了用 HashMap 来映射字符出现的个数，我们还可以映射每个数字最新的坐标，比如题目中的例子 [0,1,2,2]，遇到第一个0，映射其坐标0，遇到1，映射其坐标1，当遇到2时，映射其坐标2，每次我们都判断当前 HashMap 中的映射数，如果大于2的时候，那么需要删掉一个映射，我们还是从 start=0 时开始向右找，看每个字符在 HashMap 中的映射值是否等于当前坐标 start，比如0，HashMap 此时映射值为0，等于 left 的0，那么我们把0删掉，start 自增1，再更新结果，以此类推直至遍历完整个数组，参见代码如下：
解法二：

class Solution {
public:
int totalFruit(vector& tree) {

``````   int res = 0, start = 0, n = tree.size();
unordered_map<int, int> fruitPos;
for (int i = 0; i < n; ++i) {
fruitPos[tree[i]] = i;
while (fruitPos.size() > 2) {
if (fruitPos[tree[start]] == start) {
fruitPos.erase(tree[start]);
}
++start;
}
res = max(res, i - start + 1);
}
return res;
``````

}
};

后来又在网上看到了一种解法，这种解法是维护一个滑动窗口 sliding window，指针 left 指向起始位置，right 指向 window 的最后一个位置，用于定位 left 的下一个跳转位置，思路如下：

• 若当前字符和前一个字符相同，继续循环。

• 若不同，看当前字符和 right 指的字符是否相同：

• 若相同，left 不变，右边跳到 i - 1。

• 若不同，更新结果，left 变为 right+1，right 变为 i - 1。

``````class Solution {
public:
int totalFruit(vector<int>& tree) {
int res = 0, left = 0, right = -1, n = tree.size();
for (int i = 1; i < n; ++i) {
if (tree[i] == tree[i - 1]) continue;
if (right >= 0 && tree[right] != tree[i]) {
res = max(res, i - left);
left = right + 1;
}
right = i - 1;
}
return max(n - left, res);
}
};
``````

``````class Solution {
public:
int totalFruit(vector<int>& tree) {
int res = 0, cur = 0, cntB = 0, a = 0, b = 0;
for (int fruit : tree) {
cur = (fruit == a || fruit == b) ? cur + 1 : cntB + 1;
cntB = (fruit == b) ? cntB + 1 : 1;
if (b != fruit) {
a = b; b = fruit;
}
res = max(res, cur);
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/904