1. 題目

在一排樹中，第 i 棵樹產生 tree[i] 型的水果。
你可以從你選擇的任何樹開始，然后重復執行以下步驟：

• 把這棵樹上的水果放進你的籃子里。如果你做不到，就停下來。
• 移動到當前樹右側的下一棵樹。如果右邊沒有樹，就停下來。

請注意，在選擇一顆樹后，你沒有任何選擇：你必須執行步驟 1，然后執行步驟 2，然后返回步驟 1，然后執行步驟 2，依此類推，直至停止。

你有兩個籃子，每個籃子可以攜帶任何數量的水果，但你希望每個籃子只攜帶一種類型的水果。
用這個程序你能收集的水果總量是多少？

示例 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 個水果。提示： 1 <= tree.length <= 40000 0 <= tree[i] < tree.length

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/fruit-into-baskets
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：
LeetCode 424. 替換后的最長重復字符（滑動窗口）

• 滑動窗口，窗口內的水果種類數最多2種
• 窗口右端點一直向右擴大，左端點在水果種類 > 2種時，向右移動

class Solution { public:int totalFruit(vector<int>& tree) {unordered_map<int,int> m;int i = 0, j = 0, n = tree.size(), maxf = 0;while(j < n){if(m.size() > 2)//水果大于2種{m[tree[i]]--;//左端丟棄if(m[tree[i]]==0)m.erase(tree[i]);//計數為0，刪除i++;}m[tree[j]]++;//右端點加入if(m.size() <= 2)maxf = max(maxf, j-i+1);j++;}return maxf;} };

360 ms 57.4 MB

總結

以上是生活随笔為你收集整理的LeetCode 904. 水果成篮（滑动窗口）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。