leetcode——第904题——水果成篮

题目： 在一排树中，第 i 棵树产生 tree[i] 型的水果。 你可以从你选择的任何树开始，然后重复执行以下步骤：

把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。 移动到当前树右侧的下一棵树。如果右边没有树，就停下来。 请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。

你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。

用这个程序你能收集的水果树的最大总量是多少？

class Solution {
/*
使用滑动窗口
这题需要改动的就是因为需要两种类型，所以说需要一个 哈希表 来辨别是否已经选定了这个 tree[i]
除了需要辨别是否选定之外，还需要定义一个长度变量，因为最多只能有两种类型

所以需要用到 unordered_map(key, value) key 为tree[i]，value 为频次

坑一：关于 res 在哪里更新
    上一道题是在 while 里面更新的，这题这么操作就不对了
坑二：这里的回溯有两步，可不要少一个啊
坑三：while中要加一个 if 判断，如果符合 需要 erase 对应的元素
     对 unordered_map 的使用不熟练，好好把握
*/
public:
    int totalFruit(vector<int>& tree) 
    {
         unordered_map<int, int> basket;
        // unordered_set<int> basket; // 用这个的话就没办法回溯了，因为需要记录频次
        int res = INT_MIN, left = 0, count = 0;
        for(int j = 0; j < tree.size(); j++)
        {
            basket[tree[j]]++;
            count++;
            // basket 这个可以计算存储的数量
            while(basket.size() > 2)
            {
                basket[tree[left]]--;
                count--;    // 上面这两步是回溯

                // res = res > count ? res : count; // 错误一

                // 这个 if 用来更新，错误二：
                // 这里写错了  basket[tree[left]] 错写成 basket[left]
                if(basket[tree[left]] == 0)   basket.erase(tree[left]);
                left++; // 左区间，也就是起始位置需要右移一位
            }
            // 这个 res 必须写在 while 外面，因为有可能根本不进 while呢
            // 当然对于某些题，可以通过在 return 做一些小小的改动来达到目的，单身本题不行，
            // 因为 return res==INT_MIN?count : res 这条语句会导致更新的 res 被 count 覆盖
            res = res > count ? res : count;
        }
        return res;
    }
};