หาค่าสูงสุดใน Stack แบบ O(1) โดยไม่ใช้ Stack เพิ่มเติมใน C++

ออกแบบ Stack ที่รองรับ getMax() ใน O(1) โดยไม่ใช้พื้นที่เพิ่มเติม (O(1) Extra Space)

เทคนิค: Encode ค่าสูงสุดใน Stack เอง

เก็บค่า "Modified Value" แทนค่าจริง เมื่อ Push ค่าใหม่ที่มากกว่า Max ปัจจุบัน:

• Push: 2*x - max (Encoded Value)
• Update: max = x

เมื่อ Pop และเจอ Encoded Value (> max):

• คืนค่า Max เดิม
• Restore Max: max = 2*max - encoded

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

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

class CustomStack {
    stack stk;
    int stack_max;

public:
    void getMax() {
        if (stk.empty())
            cout << "Stack is empty\n";
        else
            cout << "Maximum Element in the stack is: " << stack_max << endl;
    }

    void peek() {
        if (stk.empty()) {
            cout << "Stack is empty\n";
            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\n";
            return;
        }
        int top = stk.top(); stk.pop();
        cout << "Top Most Element Removed: ";
        if (top > stack_max) {
            cout << stack_max << endl;
            stack_max = 2 * stack_max - top; // Restore previous max
        } else {
            cout << top << endl;
        }
    }

    void push(int element) {
        if (stk.empty()) {
            stack_max = element;
            stk.push(element);
            cout << "Element Inserted: " << element << endl;
            return;
        }
        if (element > stack_max) {
            stk.push(2 * element - stack_max); // Encode
            stack_max = element;
        } else {
            stk.push(element);
        }
        cout << "Element Inserted: " << element << endl;
    }
};

int main() {
    CustomStack stk;
    stk.push(4);
    stk.push(6);
    stk.getMax();  // 6
    stk.push(8);
    stk.push(20);
    stk.getMax();  // 20
    stk.pop();     // Remove 20
    stk.getMax();  // 8
    stk.pop();     // Remove 8
    stk.peek();    // Top = 6
    return 0;
}

ผลลัพธ์

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

ข้อจำกัด

• ทำงานได้เฉพาะ Integer (ต้องการคณิตศาสตร์ Integer)
• อาจเกิด Overflow หากค่ามากมาก (ใช้ long long ช่วยได้)
• ซับซ้อนกว่าวิธีใช้ Auxiliary Stack

วิธีทั่วไป (ใช้ Auxiliary Stack)

stack mainStack, maxStack;
void push(int x) {
    mainStack.push(x);
    if (maxStack.empty() || x >= maxStack.top()) maxStack.push(x);
}
void pop() {
    if (mainStack.top() == maxStack.top()) maxStack.pop();
    mainStack.pop();
}
int getMax() { return maxStack.top(); }