मान लीजिए हम FreqStack नामक एक स्टैक लागू करना चाहते हैं। हमारे FreqStack में दो फ़ंक्शन हैं:
push(x), यह स्टैक पर एक पूर्णांक x डालता है।
pop(), यह स्टैक में सबसे अधिक बार आने वाले तत्व को हटाता है और लौटाता है। यदि एक से अधिक तत्वों की समान आवृत्ति है, तो स्टैक के शीर्ष के सबसे करीब वाले तत्व को हटाया और लौटाया जाता है।
उदाहरण के लिए, यदि हम 7, 9, 7, 9, 6, 7 जैसे तत्वों को पुश करते हैं, फिर चार बार पॉप ऑपरेशन करते हैं, तो आउटपुट क्रमशः 7, 9, 7, 6 होगा।
हल करने का दृष्टिकोण
हम दो हैश मैप और एक अधिकतम आवृत्ति ट्रैकर का उपयोग करते हैं:
cnt[x] = तत्व x की आवृत्ति
sts[f] = आवृत्ति f वाले तत्वों का स्टैक (सबसे हालिया शीर्ष पर)
maxFreq = वर्तमान अधिकतम आवृत्ति
push: cnt अपडेट करें, maxFreq अपडेट करें, sts[cnt[x]] में डालें
pop: sts[maxFreq] से शीर्ष तत्व लें, cnt घटाएं, maxFreq अपडेट करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class FreqStack {
public:
unordered_map <int ,int > cnt;
unordered_map <int, stack <int> > sts;
int maxFreq = 0;
FreqStack() {
maxFreq = 0;
cnt.clear();
sts.clear();
}
void push(int x) {
cnt[x]++;
maxFreq = max(maxFreq, cnt[x]);
sts[cnt[x]].push(x);
}
int pop() {
int maxKey = maxFreq;
int x = sts[maxKey].top();
sts[maxKey].pop();
if(sts[maxKey].size() == 0){
sts.erase(maxKey);
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;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
return 0;
}
इनपुट
push 7, 9, 7, 9, 6, 7 फिर pop() चार बार कॉल करें
आउटपुट
7 9 7 6
