Сложность: 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 var stack: [Int]
private var maxStack: [Int]
init() {
stack = []
maxStack = []
}
func push(_ x: Int) {
stack.append(x)
if maxStack.isEmpty || x >= maxStack.last! {
maxStack.append(x)
}
}
func pop() -> Int {
let x = stack.removeLast()
if x == maxStack.last! {
maxStack.removeLast()
}
return x
}
func top() -> Int {
return stack.last!
}
func peekMax() -> Int {
return maxStack.last!
}
func popMax() -> Int {
let maxVal = maxStack.removeLast()
var buffer: [Int] = []
while stack.last! != maxVal {
buffer.append(stack.removeLast())
}
stack.removeLast()
while !buffer.isEmpty {
push(buffer.removeLast())
}
return maxVal
}
}Ставь 👍 и забирай 📚 Базу знаний