मान लीजिए कि हमारे पास पेड़ों की एक पंक्ति है, i-वें पेड़ प्रकार के पेड़ के साथ फल पैदा करता है [i]। हम अपनी पसंद के किसी भी पेड़ से शुरू कर सकते हैं, फिर इन चरणों को बार-बार करें -
- इस पेड़ के फल का एक टुकड़ा हमारी टोकरियों में डालें। अगर मौका न मिले तो रुक जाइए.
- वर्तमान पेड़ के दायीं ओर अगले पेड़ पर जाएं। अगर दाहिनी ओर कोई पेड़ नहीं है, तो रुकें।
हमारे पास दो टोकरियाँ हैं, और प्रत्येक टोकरी कितनी भी मात्रा में फल ले जा सकती है, लेकिन हम चाहते हैं कि प्रत्येक टोकरी में केवल एक ही प्रकार का फल हो। हमें यह ज्ञात करना है कि इस विधि से हम कितने फल प्राप्त कर सकते हैं? तो अगर पेड़ [0, 1, 2, 2] की तरह हैं, तो आउटपुट 3 होगा। हम [1,2,2] इकट्ठा कर सकते हैं, अगर हम पहले पेड़ से शुरू करते हैं, तो हम केवल [0, 1]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- n:=पेड़ का आकार, j:=0, उत्तर:=0
- एक नक्शा बनाएं मी
- मैं के लिए 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