สร้าง Frequency Stack ใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะสร้าง Frequency Stack ซึ่งเป็น Stack ที่การ pop() จะคืนค่า สมาชิกที่มีความถี่ (frequency) สูงสุด หากมีหลายค่าความถี่เท่ากัน ให้คืนค่าที่ ใกล้ด้านบนสุด (most recent)

ตัวอย่าง

append(7), append(9), append(7), append(9), append(6), append(7)
pop() → 7 (freq 3), pop() → 9 (freq 2, recent), pop() → 7 (freq 2), pop() → 6 (freq 1)

โครงสร้างข้อมูล

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

ขั้นตอนการทำงาน

append(x):

1. cnt[x]++
2. maxFreq = max(maxFreq, cnt[x])
3. push x เข้า sts[cnt[x]]

pop():

1. x = top ของ sts[maxFreq]
2. pop จาก sts[maxFreq]
3. ถ้า sts[maxFreq] ว่าง → ลบ key, maxFreq--
4. cnt[x]--
5. return x

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

class FreqStack {
public:
    unordered_map cnt;
    unordered_map> sts;
    int maxFreq = 0;
    
    FreqStack() {
        maxFreq = 0;
        cnt.clear();
        sts.clear();
    }
    
    void append(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.append(7);
    ob.append(9);
    ob.append(7);
    ob.append(9);
    ob.append(6);
    ob.append(7);
    
    cout << ob.pop() << endl;  // 7
    cout << ob.pop() << endl;  // 9
    cout << ob.pop() << endl;  // 7
    cout << ob.pop() << endl;  // 6
    return 0;
}

ผลลัพธ์

7
9
7
6

ความซับซ้อน

• append: O(1) amortized
• pop: O(1) amortized
• พื้นที่: O(n)

สรุป

Frequency Stack ใช้ hash map + map of stacks จัดการความถี่และลำดับเวลาได้ O(1) เป็นโจทย์คลาสสิก (LeetCode 895) หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ