หาค่าสูงสุดใน Stack แบบ O(1) Time และ O(1) Extra Space ใน C++

โจทย์

ออกแบบ Stack ที่รองรับการดึงค่าสูงสุด (getMax) ใน O(1) โดยใช้ Extra Space แค่ O(1) (ไม่ใช้ Stack/Array เพิ่ม)

เทคนิค (Encoding ใน Stack เอง)

เก็บค่า "เข้ารหัส" แทนค่าจริง:

• Push x: ถ้า x > max ปัจจุบัน → push (2*x - max), อัปเดต max = x; มิฉะนั้น push x ปกติ
• Pop: ถ้า top > max → ค่าจริงคือ max, อัปเดต max = 2*max - top; มิฉะนั้นค่าจริงคือ top
• Peek: ค่าจริง = min(top, max)
• GetMax: คืนค่า max โดยตรง

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

#include <iostream>
#include <stack>
using namespace std;

class CustomStack {
    stack<int> stk;
    int stack_max;
public:
    void getMax() {
        if (stk.empty()) cout << "Stack is empty" << endl;
        else cout << "Maximum Element in the stack is: " << stack_max << endl;
    }
    void peek() {
        if (stk.empty()) { cout << "Stack is empty "; return; }
        int top = stk.top();
        cout << "Top Most Element is: " << ((top > stack_max) ? stack_max : top) << endl;
    }
    void pop() {
        if (stk.empty()) { cout << "Stack is empty" << endl; return; }
        cout << "Top Most Element Removed: ";
        int top = stk.top(); stk.pop();
        if (top > stack_max) {
            cout << stack_max << endl;
            stack_max = 2 * stack_max - top;
        } else cout << top << endl;
    }
    void push(int element) {
        if (stk.empty()) { stack_max = element; stk.push(element); }
        else if (element > stack_max) { stk.push(2 * element - stack_max); stack_max = element; }
        else stk.push(element);
        cout << "Element Inserted: " << element << endl;
    }
};

int main() {
    CustomStack stk;
    stk.push(4);
    stk.push(6);
    stk.getMax();
    stk.push(8);
    stk.push(20);
    stk.getMax();
    stk.pop();
    stk.getMax();
    stk.pop();
    stk.peek();
}

ผลลัพธ์

Element Inserted: 4
Element Inserted: 6
Maximum Element in the stack is: 6
Element Inserted: 8
Element Inserted: 20
Maximum Element in the stack is: 20
Top Most Element Removed: 20
Maximum Element in the stack is: 8
Top Most Element Removed: 8
Top Most Element is: 6