[LeetCode]Fruit Into Baskets

原题

In a row of trees, the i -th tree produces fruit with type  tree[i] .

You start at any tree of your choice , then repeatedly perform the following steps:

1. Add one piece of fruit from this tree to your baskets.  If you cannot, stop.
2. Move to the next tree to the right of the current tree.  If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Example 1:

Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].

Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].

Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].

Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.

Note:

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

题解

该题属于双指针（Two Pointers）范畴，主要的思路是利用两个指针来构造一个滑动窗口，且要求窗口中的元素类型不得超过2种。所以，经过一遍for循环，即可拿到所有不超过两个类型元素的窗口长度，即拿到其中最大的长度。

所以，难度在于怎么来构造这个窗口。这里，我们可以巧妙的利用映射（Map）这种数据结构，用映射来维护for循环过程中，经过的数据类型总数，以及每种类型的个数。

以原题中第一个案例为例，在第一次for循环中，我们将第一个元素加入到map中，如下：

map m;

m.insert(make_pair(1, 1)); // 第一个元素代表类型为1，第二个元素代表类型为1的出现的个数

同时，可以很容易的拿到某时刻的状态信息：

m.size(); // 当前不同类型的总数

m.find(1)->second; // 类型为1的出现的次数

代码

class Solution {
    public:
        int totalFruit(vector<int>& tree) {
            map<int, int> m;
            map<int, int>::iterator it;
            int l = 0, r = 0, len = tree.size(), a = 0;
            while (r < len) {
                if (m.size() <= 2) {
                    it = m.find(tree[r]);
                    if (it != m.end()) {
                        it->second++;
                        m.insert(make_pair(tree[r], it->second + 1));
                    } else {
                        m.insert(make_pair(tree[r], 1));
                    }
                    r++;
                    if (a < r - l) a = r - l;
                } else {
                    it = m.find(tree[l]);
                    m.erase(tree[l]);
                    if (it->second != 1) {
                        m.erase(tree[l]);
                        m.insert(make_pair(tree[l], it->second - 1));
                        it = m.find(tree[l]);
                    }
                    l++; 
                }
            }
            return a;
        }
};

原题： https://leetcode.com/problems/fruit-into-baskets/description/

Github 源码： https://github.com/GenialX/leetcode-cpp/blob/master/2018/09/fruit-into-baskets.cpp

文章来源： 胡小旭 =>  [LeetCode]Fruit Into Baskets