用C ++将水果放入篮子

假设我们有一排树，第i棵树产生的树的类型为tree [i]。我们可以从我们选择的任何树开始，然后重复执行这些步骤-

• 从这棵树上添加一块水果到我们的篮子里。如果没有机会，请停止。

• 移至当前树右侧的下一棵树。如果右边没有树，请停止。

我们有两个篮子，每个篮子可以装任何数量的水果，但是我们希望每个篮子只能装一种水果。我们必须找到可以通过此程序收集的水果总量吗？因此，如果树是[0，1，2，2]，则输出将为3。我们可以收集[1,2,2]，如果我们从第一棵树开始，那么我们只会收集[0，1， 1]

为了解决这个问题，我们将遵循以下步骤-

• n：=树大小，j：= 0，ans：= 0

• 创建一张映射

• 对于i，范围为0至n – 1

• 将m [tree [j]]减少1

• 如果m [tree [j]] = 0，则从m中删除tree [j]

• 将j增加1

• 将m [tree [i]]增加1

• 当m的大小> 2且j <= i时，则

• ans：= i – j + 1和ans的最大值

• 返回ans

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int totalFruit(vector<int>& tree) {
      int n = tree.size();
      int j = 0;
      map <int, int> m;
      int ans = 0;
      for(int i = 0; i < n; i++){
         m[tree[i]] += 1;
         while(m.size() > 2 && j <= i){
            m[tree[j]]--;
            if(m[tree[j]] == 0)m.erase(tree[j]);
            j++;
         }
         ans = max(i - j + 1, ans);
      }
      return ans;
   }
};
main(){
   vector<int> v = {3,3,3,1,2,1,1,2,3,3,4};
   Solution ob;
   cout <<(ob.totalFruit(v));
}

输入项

[3,3,3,1,2,1,1,2,3,3,4]

输出结果

5