904.Fruit Into Baskets
===

###### tags: `Medium`,`Array`,`Hash Table`,`Sliding Window`

[904. Fruit Into Baskets](https://leetcode.com/problems/fruit-into-baskets/)

### 題目描述

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array `fruits` where `fruits[i]` is the **type** of fruit the i^th^ tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

* You only have **two** baskets, and each basket can only hold a **single type** of fruit. There is no limit on the amount of fruit each basket can hold.
* Starting from any tree of your choice, you must pick **exactly one fruit** from **every** tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
* Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array `fruits`, return *the **maximum** number of fruits you can pick.*

### 範例

**Example 1:**

Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.

**Example 2:**

Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].

**Example 3:**

Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].

**Constraints**:

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

### 解答
#### C++

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

> [name=Yen-Chi Chen][time=Tue, Feb 7, 2023]

##### 思路2:
1. 找subarray, 此subarray只有兩種數字且長度是所有可能中最長的
2. 遍歷array, 遇到一個數字時, 若目前出現種類小於兩個, 或等於兩個且有出現在這兩個之中, 則當前subarray長度+1即可
3. 遇到第三種數字時, 新的subarray起點會是前一個數字往前推直到數字有變的地方為起點, 因此數字有變時要記錄index預備新array的起點, 重新計算長度

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_set<int> s;
        int prev_start_index = 0, res = 1, cur_length = 1;
        s.insert(fruits[0]);
        for(int i = 1; i < fruits.size(); i++)
        {
            if(fruits[i] == fruits[i-1])
                cur_length++;
            else
            {
                if(s.size() < 2)
                    s.insert(fruits[i]);
                else
                {
                    if(!s.count(fruits[i]))
                    {
                        cur_length = i - prev_start_index;
                        int too_far_n = -1;
                        for(auto n : s)
                        {
                            if(n != fruits[i-1])
                                too_far_n = n;
                        }
                        s.erase(too_far_n);
                        s.insert(fruits[i]);
                    }
                }
                cur_length++;
                prev_start_index = i;
            }            
            res = max(res, cur_length);
        }
        return res;
    }
};

Time: $O(n)$
Extra Space: $O(1)$

> [name=XD] [time= Feb 7, 2023]

#### Python

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        ans, l = 0, 0
        cnt = Counter()
        for r, fruit in enumerate(fruits):
            cnt[fruit] += 1
            while len(cnt) > 2:
                cnt[fruits[l]] -= 1
                if cnt[fruits[l]] == 0:
                    del cnt[fruits[l]]
                l += 1
            ans = max(ans, r - l + 1)
        return ans

> [name=Yen-Chi Chen][time=Tue, Feb 7, 2023]

#### Javascript

function totalFruit(fruits) {
  let left = 0;
  let max = 0;
  let count = 0;
  const baskets = [];
  for (let i = 0; i < fruits.length; i++) {
    if (baskets.includes(fruits[i])) {
      count++;
    } else {
      if (baskets.length < 2) {
        baskets.push(fruits[i]);
        count++;
      } else {
        // 往前找到第一個不同的水果
        for (let j = i - 1; j >= left; j--) {
          if (fruits[j] !== fruits[i - 1]) {
            left = j + 1; // 更新起始點
            break;
          }
        }
        // 重新裝水果
        baskets[0] = fruits[i - 1];
        baskets[1] = fruits[i];
        count = i - left + 1;
      }
    }

    max = Math.max(max, count);
  }

  return max;
}

> 參考前面兩位大神的解法寫出來了，感恩兩位大神！
> [name=Marsgoat][time=Feb 9, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)