Max Stack
Leetcode #716 | Hard | Стек | Связный список | Хэш-таблицы | Деревья | Куча | Design
Идея
Вариант 1. Два стека, один накапливает значения, другой для максимумов каждого состояния. При popMax() снимаем со второго стека, создаем буфер, берем значения из первого и ложим в буфер, когда дошли до максимума удаляем его а из буфера все возвращаем. Все операции кроме popMax() за O(1), popMax() - O(n)
Вариант 2. Связный список + TreeMap (красно-черное дерево, там удалить/добавить элемент в любое место log(n) и узнать максимум тоже). Заводим свои Node, в TreeMap храним ключ - лист нод, при добавлении одинаковых элементов цепляем просто к листу, максимум отдает treemap. Все операции за O(log(n))
Big-O
- Время
O(log(N)) - Память
O(N)
Код
class MaxStack {
class Node {
int val; Node prev, next;
Node(int v) { val = v; }
}
private Node head = new Node(0), tail = new Node(0);
private TreeMap<Integer, List<Node>> map = new TreeMap<>();
public MaxStack() { head.next = tail; tail.prev = head; }
public void push(int x) {
Node node = new Node(x);
Node prev = tail.prev; prev.next = node; node.prev = prev; node.next = tail; tail.prev = node;
map.computeIfAbsent(x, k -> new ArrayList<>()).add(node);
}
public int pop() {
Node node = tail.prev; unlink(node);
List<Node> list = map.get(node.val); list.remove(list.size() - 1);
if (list.isEmpty()) map.remove(node.val);
return node.val;
}
public int top() { return tail.prev.val; }
public int peekMax() { return map.lastKey(); }
public int popMax() {
int maxVal = map.lastKey();
List<Node> list = map.get(maxVal);
Node node = list.remove(list.size() - 1);
if (list.isEmpty()) map.remove(maxVal);
unlink(node);
return maxVal;
}
private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
}