C++로 과일 바구니에 담기

<시간/>

나무 행이 있다고 가정하고 i번째 나무는 tree[i] 유형의 과일을 생산합니다. 선택한 트리에서 시작한 다음 이 단계를 반복적으로 수행할 수 있습니다. −

우리 바구니에 이 나무의 과일 한 조각을 추가하십시오. 기회가 없으면 중지하십시오.
현재 트리의 오른쪽에 있는 다음 트리로 이동합니다. 오른쪽에 나무가 없으면 정지하세요.

우리에게는 두 개의 바구니가 있고 각 바구니에는 과일의 양에 상관없이 담을 수 있지만 각 바구니에는 각각 한 가지 유형의 과일만 담을 수 있기를 바랍니다. 이 절차로 모을 수 있는 과일의 총량을 찾아야 합니까? 따라서 트리가 [0, 1, 2, 2]와 같으면 출력은 3이 됩니다. [1,2,2]를 수집할 수 있습니다. 첫 번째 트리에서 시작하면 [0, 1]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=트리 크기, j :=0, ans :=0
하나의 지도 만들기 m
0 ~ n – 1 범위의 i에 대해
- m[tree[i]] 1 증가
- m의 크기가> 2이고 j <=i인 경우
  - m[tree[j]] 1 감소
  - m[tree[j]] =0이면 m에서 tree[j] 삭제
  - j를 1 증가
- ans :=i – j + 1 및 an의 최대값
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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]