> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/array/904.-fruit-into-baskets.md).

# 904. Fruit Into Baskets

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:

1. Add one piece of fruit from this tree to your baskets.  If you cannot, stop.
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`

{% hint style="info" %}
要求longest subarray with only 2 distinct numbers，可以利用sliding window用two pointers紀錄start和end位置，還有hashmap來記錄number出現次數來計算。
{% endhint %}

```cpp
// Sliding Window
int totalFruit(vector<int>& tree) { // time: O(n); space: O(1)
    unordered_map<int, int> m;
    int res = 0, i = 0; // i is start, j is end
    for (int j = 0; j < tree.size(); ++j) {
        ++m[tree[j]];
        while (m.size() > 2) {
            --m[tree[i]];
            if (m[tree[i]] == 0) m.erase(tree[i]);
            ++i;
        }
        res = max(res, j - i + 1);
    }
    return res;
}
```

{% hint style="info" %}
優化空間使用，分成3種cases來考慮。res代表global result，cur代表local result，count\_second代表第二種水果連續出現的數量。

1. 當前的水果等於第二種水果:

   local result + 1\
   第二種水果的連續數量+1
2. 當前的水果等於第一種水果:\
   local result + 1\
   此時原本的第二種水果不是連續出現了，要把原本第二種水果當成新的第一種水果，然後新的第二種水果為當前遇到的水果，在這case下就是原本的第一種水果。\
   要重設第二種水果連續出現次數為1
3. 當前的水果不等於已經看得到兩種水果:\
   原本的第二種水果並非連續出現了，重新設定新的第一種水果為原本第二種水果，捨棄原本第一種水果，然後把新的第二種水果設為當前遇到的水果。\
   local result 設為原先第二種水果連續出現次數+1\
   重設第二種水果連續出現次數為1
   {% endhint %}

```cpp
int totalFruit(vector<int>& tree) { // time: O(n); space: O(1)
    int res = 0, cur = 0, first = 0, second = 0, count_second = 0;
    for (int fruit : tree) {
        if (fruit == second) {
            cur += 1;
            count_second += 1;
        } else if (fruit == first) {
            cur += 1;
            count_second = 1;
            first = second;
            second = fruit;
        } else {
            cur = count_second + 1;
            count_second = 1;
            first = second;
            second = fruit;
        }
        res = max(res, cur);
    }
    return res;
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/array/904.-fruit-into-baskets.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.