Задача: 716. Max Stack
Сложность: hard

Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.

Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

👨‍💻 Алгоритм:

1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов.

2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека.

3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно.

😎 Решение:

class MaxStack {
public:
    MaxStack() {}

    void push(int x) {
        stack.push(x);
        if (maxStack.empty() || x >= maxStack.top()) {
            maxStack.push(x);
        }
    }

    int pop() {
        int x = stack.top();
        stack.pop();
        if (x == maxStack.top()) {
            maxStack.pop();
        }
        return x;
    }

    int top() {
        return stack.top();
    }

    int peekMax() {
        return maxStack.top();
    }

    int popMax() {
        int maxVal = maxStack.top();
        maxStack.pop();
        stack<int> buffer;
        while (stack.top() != maxVal) {
            buffer.push(stack.top());
            stack.pop();
        }
        stack.pop();
        while (!buffer.empty()) {
            push(buffer.top());
            buffer.pop();
        }
        return maxVal;
    }

private:
    stack<int> stack;
    stack<int> maxStack;
};

Ставь 👍 и забирай 📚 Базу знаний