สร้าง Maximum Stack รองรับ popmax() ใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะสร้าง Maximum Stack ซึ่งเป็น Stack ที่รองรับการดึงค่าสูงสุด (max) และลบค่าสูงสุด (popmax) ได้ใน O(log n)

การดำเนินการที่รองรับ

• MaxStk() - สร้าง instance ใหม่
• push(val) - เพิ่มค่าเข้า stack
• top() - ดูค่าบนสุด
• max() - ดูค่าสูงสุด
• pop() - ลบและคืนค่าบนสุด
• popmax() - ลบและคืนค่าสูงสุด

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

ใช้ 2 Sets (BST):

• stk: เก็บคู่ (position_index, value) เรียงตาม position (เพื่อ top/pop)
• aux: เก็บคู่ (value, position_index) เรียงตาม value (เพื่อ max/popmax)

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

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

class MaxStk {
    int pos_index = 0;
    set, greater<>> stk;  // (pos, val) เรียง pos มาก->น้อย
    set, greater<>> aux;  // (val, pos) เรียง val มาก->น้อย
    
public:
    MaxStk() {}
    
    void push(int val) {
        stk.emplace(pos_index, val);
        aux.emplace(val, pos_index);
        pos_index++;
    }
    
    int top() {
        if (stk.empty()) return -1;
        return stk.begin()->second;
    }
    
    int max() {
        if (aux.empty()) return -1;
        return aux.begin()->first;
    }
    
    int pop() {
        if (stk.empty()) return -1;
        int id = stk.begin()->first;
        int ret = stk.begin()->second;
        stk.erase(stk.begin());
        aux.erase({ret, id});
        return ret;
    }
    
    int popmax() {
        if (aux.empty()) return -1;
        int ret = aux.begin()->first;
        int id = aux.begin()->second;
        aux.erase(aux.begin());
        stk.erase({id, ret});
        return ret;
    }
};

int main() {
    MaxStk max_stk;
    max_stk.push(5);
    max_stk.push(15);
    max_stk.push(10);
    
    cout << max_stk.top() << endl;    // 10
    cout << max_stk.max() << endl;    // 15
    cout << max_stk.popmax() << endl; // 15
    cout << max_stk.max() << endl;    // 10
    cout << max_stk.pop() << endl;    // 10
    cout << max_stk.top() << endl;    // 5
    return 0;
}

ผลลัพธ์

10
15
15
10
10
5

ความซับซ้อน

• push, top, max, pop, popmax: O(log n)
• พื้นที่: O(n)

สรุป

ใช้ 2 Sets (BST) จัดการ stack และ max พร้อมกัน รองรับ popmax() ได้อย่างมีประสิทธิภาพ หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ