ট্রি অ্যারে দেওয়া, tree[i] = i-তম ট্রির ফলের টাইপ। দুইটি বাস্কেট, প্রতিটি এক টাইপের ফল ধারণ করতে পারে। যেকোনো ট্রি থেকে শুরু করে ডানদিকে যেতে হবে। সর্বোচ্চ কতটি ফল সংগ্রহ করা যায়?
উদাহরণ: [3,3,3,1,2,1,1,2,3,3,4] → ৫ ([1,2,1,1,2] বা [2,1,1,2,3])।
সমাধানের ধাপসমূহ
- স্লাইডিং উইন্ডো: मैপ
mফলের টাইপ -> কাউন্ট। - রাইট পয়েন্টার
iবাড়ান,m[tree[i]]++। - যদি
m.size() > 2হয়, লেফট পয়েন্টারjবাড়িয়ে উইন্ডো সঙ্কুচিত করুন (m[tree[j]]--, ০ হলে erase)। - উত্তর = max(ans, i-j+1)।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int totalFruit(vector<int>& tree) {
unordered_map<int, int> m;
int j = 0, ans = 0, n = tree.size();
for (int i = 0; i < n; i++) {
m[tree[i]]++;
while (m.size() > 2) {
if (--m[tree[j]] == 0) m.erase(tree[j]);
j++;
}
ans = max(ans, i - j + 1);
}
return ans;
}
};
int 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
