ধরুন আমাদের সারি সারি গাছ আছে, i-th গাছটি গাছের সাথে ফল দেয় [i]। আমরা আমাদের পছন্দের যেকোনো গাছ থেকে শুরু করতে পারি, তারপরে বারবার এই ধাপগুলি সম্পাদন করতে পারি −
- আমাদের ঝুড়িতে এই গাছ থেকে এক টুকরো ফল যোগ করুন। যদি কোন সুযোগ না থাকে, তাহলে থামুন।
- বর্তমানের ডানদিকে পরবর্তী গাছে যান। যদি ডানদিকে কোন গাছ না থাকে, তাহলে থামুন।
আমাদের দুটি ঝুড়ি আছে, এবং প্রতিটি ঝুড়ি যেকোনো পরিমাণ ফল বহন করতে পারে, কিন্তু আমরা চাই প্রতিটি ঝুড়িতে শুধুমাত্র এক ধরনের ফল বহন করা উচিত। এই পদ্ধতির মাধ্যমে আমরা মোট কত ফল সংগ্রহ করতে পারি তা খুঁজে বের করতে হবে? তাই গাছগুলো যদি [0, 1, 2, 2] এর মত হয়, তাহলে আউটপুট হবে 3। আমরা সংগ্রহ করতে পারি [1,2,2], যদি আমরা প্রথম গাছ থেকে শুরু করি, তাহলে আমরা শুধুমাত্র [0, 1]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=গাছের আকার, j :=0, উত্তর :=0
- একটি মানচিত্র তৈরি করুন m
- আমি 0 থেকে n – 1
- পরিসরে
- m[tree[i]] 1 দ্বারা বাড়ান
- যখন m-এর মাপ> 2 এবং j <=i, তারপর
- m[tree[j]] 1 দ্বারা কমিয়ে দিন
- যদি m[tree[j]] =0 হয়, তাহলে m থেকে ট্রি[j] মুছে দিন
- j 1 দ্বারা বাড়ান
- উত্তর :=i – j + 1 এবং উত্তরের সর্বোচ্চ
- উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
