Tìm phần tử lớn nhất trong stack O(1) thời gian và O(1) bộ nhớ phụ trong C++

Thiết kế stack có thể trả về phần tử lớn nhất trong O(1) thời gian, chỉ dùng O(1) bộ nhớ thêm. Kỹ thuật: lưu giá trị được biến đổi khi push phần tử mới lớn hơn max hiện tại.

• Push(x): Nếu stack rỗng, max = x, push(x). Nếu x > max, push(2*x - max), cập nhật max = x. Ngược lại push(x).
• Pop(): Nếu top > max, phần tử bị loại thực sự là max, cập nhật max = 2*max - top. Trả về max cũ.
• Peek(): Trả về min(top, max).
• GetMax(): Trả về max.

Ví dụ

#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: " << endl;
        (top > stack_max) ? cout << stack_max : cout << top;
    }
    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);
            cout << "Element Inserted: " << element << endl;
            return;
        }
        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();
}

Kết quả

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