在一排樹中藻雌，第 i 棵樹產(chǎn)生 tree[i] 型的水果雌续。
你可以從你選擇的任何樹開始，然后重復(fù)執(zhí)行以下步驟：把這棵樹上的水果放進(jìn)你的籃子里胯杭。如果你做不到驯杜，就停下來。
移動(dòng)到當(dāng)前樹右側(cè)的下一棵樹做个。如果右邊沒有樹鸽心，就停下來。
請(qǐng)注意居暖，在選擇一顆樹后顽频，你沒有任何選擇：你必須執(zhí)行步驟 1，然后執(zhí)行步驟 2太闺，然后返回步驟 1糯景，然后執(zhí)行步驟 2，依此類推省骂，直至停止蟀淮。你有兩個(gè)籃子，每個(gè)籃子可以攜帶任何數(shù)量的水果钞澳，但你希望每個(gè)籃子只攜帶一種類型的水果怠惶。
用這個(gè)程序你能收集的水果總量是多少？示例 1：
輸入：[1,2,1]
輸出：3
解釋：我們可以收集 [1,2,1]略贮。
示例 2：輸入：[0,1,2,2]
輸出：3
解釋：我們可以收集 [1,2,2].
如果我們從第一棵樹開始甚疟，我們將只能收集到 [0, 1]仗岖。
示例 3：輸入：[1,2,3,2,2]
輸出：4
解釋：我們可以收集 [2,3,2,2].
如果我們從第一棵樹開始，我們將只能收集到 [1, 2]览妖。
示例 4：輸入：[3,3,3,1,2,1,1,2,3,3,4]
輸出：5
解釋：我們可以收集 [1,2,1,1,2].
如果我們從第一棵樹或第八棵樹開始轧拄，我們將只能收集到 4 個(gè)水果。
解題思路
這題其實(shí)要求其實(shí)很簡(jiǎn)單讽膏，就是找出數(shù)組中長(zhǎng)度最大的連續(xù)由2種元素構(gòu)成的子數(shù)組檩电，返回這個(gè)子數(shù)組的長(zhǎng)度。但由于本題有時(shí)間限制府树，只是樸素的解法會(huì)出現(xiàn)超時(shí)的情況俐末，需要對(duì)實(shí)現(xiàn)進(jìn)行一定的優(yōu)化。
參考花花醬的hashtable+ sliding windows
class Solution {
public:
// 樸素解法
int totalFruit(vector<int>& tree) {
int size = tree.size();
int fruit[size] = {0};
int max =0;
for(int i = 0; i< size;i++){
int number = 1;
int type1 = -1;
// 第一種水果
type1 = tree[i];
int type2 = -1;
for(int j = i+1; j<size ;j++){
// 第二種水果
if(tree[j]!=tree[i]){
// type2 is null
if(type2 < 0){
type2 = tree[j];
number++;
}else{
// 出現(xiàn)第三種水果奄侠，跳出循環(huán)
if(tree[j] != type2){
break;
}else{
number++;
}
}
}else{
number++;
}
}
fruit[i] = number;
if(number> max)
max = number;
}
return max;
}
public:
// by [花花醬] (https://zxi.mytechroad.com/blog/hashtable/leetcode-904-fruit-into-baskets/)
int totalFruit(vector<int>& tree) {
map<int, int> idx; // {fruit -> last_index}
int ans = 0;
int cur = 0;
for (int i = 0; i < tree.size(); ++i) {
int f = tree[i]; // 取一種水果
if (!idx.count(f)) { // 返回值只有0或1
// !idx.count(f) == 1,即出現(xiàn)某種新水果時(shí)
if (idx.size() == 2) { // 如果已經(jīng)有了兩種水果卓箫，再出現(xiàn)第三種水果的時(shí)候
auto it1 = begin(idx);
auto it2 = next(it1);
if (it1->second > it2->second) swap(it1, it2);
// 找到之前兩種水果中，下標(biāo)最小的水果垄潮，開始新的窗口
cur = i - it1->second - 1; // cur存新窗口的大小
idx.erase(it1); // 刪除下標(biāo)較小的水果
}
}
// 添加新水果的下標(biāo)信息
idx[f] = i;
// 比較新窗口和上一個(gè)窗口的大小
ans = max(++cur, ans);
}
return ans;
}
};
