Ngăn xếp tần suất tối đa trong C++

Triển khai FreqStack với push(x) và pop(): pop trả về phần tử xuất hiện nhiều nhất; nếu bằng nhau, lấy phần tử gần đỉnh nhất.

Ví dụ: push 7,9,7,9,6,7 → pop 4 lần: 7,9,7,6.

Giải thuật

1. Dùng map cnt[x] lưu tần suất hiện tại của x.
2. Dùng map sts[f] lưu stack các phần tử có tần suất f (theo thứ tự push).
3. maxFreq lưu tần suất lớn nhất hiện có.
4. push(x): tăng cnt[x], cập nhật maxFreq, push x vào sts[cnt[x]].
5. pop(): lấy top của sts[maxFreq], xóa, giảm cnt[x], nếu sts[maxFreq] rỗng thì xóa và giảm maxFreq.

Ví dụ mã C++

#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;
}

Đầu vào

push 7,9,7,9,6,7 rồi pop() 4 lần

Đầu ra

7 9 7 6