สแต็กความถี่สูงสุดใน C++ (FreqStack)

คำอธิบายปัญหา

ออกแบบ FreqStack รองรับ:

• push(x): ใส่ x เข้า stack
• pop(): ลบและคืนค่าที่มีความถี่มากที่สุด ถ้ามีหลายค่า ให้คืนตัวที่ใกล้ top มากที่สุด

ตัวอย่าง

push: 7,9,7,9,6,7 → pop×4: 7, 9, 7, 6

แนวทางแก้ปัญหา: HashMap + Stack of Stacks

• cnt[x]: ความถี่ของ x
• sts[f]: stack ของค่าที่มีความถี่ f (ล่าสุดอยู่บนสุด)
• maxFreq: ความถี่สูงสุดปัจจุบัน

push(x):

li>cnt[x]++
1. maxFreq = max(maxFreq, cnt[x])
2. sts[cnt[x]].push(x)

pop():

1. x = sts[maxFreq].top(); sts[maxFreq].pop()
2. ถ้า sts[maxFreq] ว่าง → maxFreq--
3. cnt[x]--
4. คืน x

ตัวอย่างโค้ด 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:
    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;
    }
};

ความซับซ้อน

• push: O(1) amortized
• pop: O(1) amortized
• พื้นที่: O(n) สำหรับ n elements