Задача: 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 {

    private val stack = mutableListOf<Int>()
    private val maxStack = mutableListOf<Int>()

    fun push(x: Int) {
        stack.add(x)
        if (maxStack.isEmpty() || x >= maxStack.last()) {
            maxStack.add(x)
        }
    }

    fun pop(): Int {
        val x = stack.removeAt(stack.size - 1)
        if (x == maxStack.last()) {
            maxStack.removeAt(maxStack.size - 1)
        }
        return x
    }

    fun top(): Int {
        return stack.last()
    }

    fun peekMax(): Int {
        return maxStack.last()
    }

    fun popMax(): Int {
        val maxVal = maxStack.removeAt(maxStack.size - 1)
        val buffer = mutableListOf<Int>()
        while (stack.last() != maxVal) {
            buffer.add(stack.removeAt(stack.size - 1))
        }
        stack.removeAt(stack.size - 1)
        while (buffer.isNotEmpty()) {
            push(buffer.removeAt(buffer.size - 1))
        }
        return maxVal
    }
}       }
        stack.pop();
        while (!buffer.empty()) {
            push(buffer.top());
            buffer.pop();
        }
        return maxVal;
    }

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

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