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