সমস্যা বিবরণ
FreqStack ক্লাস বাস্তবায়ন করতে হবে যাতে:
- push(x) — x স্টকে পুশ করুন।
- pop() — সবচেয়ে বেশি ফ্রিকোয়েন্সি वाला এলিমেন্ট রিটার্ন করুন। টাই হলে টপের কাছাকাছি এলিমেন্ট।
উদাহরণ
push: 7,9,7,9,6,7 → pop() x4: 7, 9, 7, 6
সমাধান পদ্ধতি
- cnt[x] = x-এর ফ্রিকোয়েন্সি।
- sts[f] = ফ্রিকোয়েন্সি f বিশিষ্ট এলিমেন্টগুলোর স্ট্যাক।
- maxFreq = বর্তমান সর্বোচ্চ ফ্রিকোয়েন্সি।
- push: cnt[x]++, sts[cnt[x]].push(x), maxFreq আপডেট।
- pop: sts[maxFreq].top() রিটার্ন, স্ট্যাক খালি হলে maxFreq--।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class FreqStack {
unordered_map<int, int> cnt;
unordered_map<int, stack<int>> sts;
int maxFreq = 0;
public:
FreqStack() { maxFreq = 0; }
void push(int x) {
cnt[x]++;
maxFreq = max(maxFreq, cnt[x]);
sts[cnt[x]].push(x);
}
int pop() {
int x = sts[maxFreq].top();
sts[maxFreq].pop();
if (sts[maxFreq].empty()) {
sts.erase(maxFreq);
maxFreq--;
}
cnt[x]--;
return x;
}
};
int main() {
FreqStack ob;
ob.push(7); ob.push(9); ob.push(7);
ob.push(9); ob.push(6); ob.push(7);
cout << ob.pop() << endl; // 7
cout << ob.pop() << endl; // 9
cout << ob.pop() << endl; // 7
cout << ob.pop() << endl; // 6
return 0;
}ইনপুট ও আউটপুট
ইনপুট: push 7,9,7,9,6,7 → pop() x4
আউটপুট: 7 9 7 6
