904.Fruit Into Baskets

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

題目描述

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⁵
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;
    }
};

Yen-Chi ChenTue, Feb 7, 2023

思路2:

找subarray, 此subarray只有兩種數字且長度是所有可能中最長的
遍歷array, 遇到一個數字時, 若目前出現種類小於兩個, 或等於兩個且有出現在這兩個之中, 則當前subarray長度+1即可
遇到第三種數字時, 新的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)

XD 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

Yen-Chi ChenTue, 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;
}

參考前面兩位大神的解法寫出來了，感恩兩位大神！
MarsgoatFeb 9, 2023

Reference

回到題目列表