Question

716. Max Stack

中文文档

Description

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the MaxStack class:

• MaxStack() Initializes the stack object.
• void push(int x) Pushes element x onto the stack.
• int pop() Removes the element on top of the stack and returns it.
• int top() Gets the element on the top of the stack without removing it.
• int peekMax() Retrieves the maximum element in the stack without removing it.
• int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

You must come up with a solution that supports O(1) for each top call and O(logn) for each other call.

 

Example 1:

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]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();   // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();   // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();   // return 1, [5] the top of the stack and the max element is now 5.
stk.top();   // return 5, [5] the stack did not change.

 

Constraints:

• -107 <= x <= 107
• At most 105 calls will be made to push, pop, top, peekMax, and popMax.
• There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

Solutions

Solution 1

from sortedcontainers import SortedList


class Node:
  def __init__(self, val=0):
    self.val = val
    self.prev: Union[Node, None] = None
    self.next: Union[Node, None] = None


class DoubleLinkedList:
  def __init__(self):
    self.head = Node()
    self.tail = Node()
    self.head.next = self.tail
    self.tail.prev = self.head

  def append(self, val) -> Node:
    node = Node(val)
    node.next = self.tail
    node.prev = self.tail.prev
    self.tail.prev = node
    node.prev.next = node
    return node

  @staticmethod
  def remove(node) -> Node:
    node.prev.next = node.next
    node.next.prev = node.prev
    return node

  def pop(self) -> Node:
    return self.remove(self.tail.prev)

  def peek(self):
    return self.tail.prev.val


class MaxStack:
  def __init__(self):
    self.stk = DoubleLinkedList()
    self.sl = SortedList(key=lambda x: x.val)

  def push(self, x: int) -> None:
    node = self.stk.append(x)
    self.sl.add(node)

  def pop(self) -> int:
    node = self.stk.pop()
    self.sl.remove(node)
    return node.val

  def top(self) -> int:
    return self.stk.peek()

  def peekMax(self) -> int:
    return self.sl[-1].val

  def popMax(self) -> int:
    node = self.sl.pop()
    DoubleLinkedList.remove(node)
    return node.val


# Your MaxStack object will be instantiated and called as such:
# obj = MaxStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.peekMax()
# param_5 = obj.popMax()

class Node {
  public int val;
  public Node prev, next;

  public Node() {
  }

  public Node(int val) {
    this.val = val;
  }
}

class DoubleLinkedList {
  private final Node head = new Node();
  private final Node tail = new Node();

  public DoubleLinkedList() {
    head.next = tail;
    tail.prev = head;
  }

  public Node append(int val) {
    Node node = new Node(val);
    node.next = tail;
    node.prev = tail.prev;
    tail.prev = node;
    node.prev.next = node;
    return node;
  }

  public static Node remove(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    return node;
  }

  public Node pop() {
    return remove(tail.prev);
  }

  public int peek() {
    return tail.prev.val;
  }
}

class MaxStack {
  private DoubleLinkedList stk = new DoubleLinkedList();
  private TreeMap<Integer, List<Node>> tm = new TreeMap<>();

  public MaxStack() {
  }

  public void push(int x) {
    Node node = stk.append(x);
    tm.computeIfAbsent(x, k -> new ArrayList<>()).add(node);
  }

  public int pop() {
    Node node = stk.pop();
    List<Node> nodes = tm.get(node.val);
    int x = nodes.remove(nodes.size() - 1).val;
    if (nodes.isEmpty()) {
      tm.remove(node.val);
    }
    return x;
  }

  public int top() {
    return stk.peek();
  }

  public int peekMax() {
    return tm.lastKey();
  }

  public int popMax() {
    int x = peekMax();
    List<Node> nodes = tm.get(x);
    Node node = nodes.remove(nodes.size() - 1);
    if (nodes.isEmpty()) {
      tm.remove(x);
    }
    DoubleLinkedList.remove(node);
    return x;
  }
}

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack obj = new MaxStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.peekMax();
 * int param_5 = obj.popMax();
 */

class MaxStack {
public:
  MaxStack() {
  }

  void push(int x) {
    stk.push_back(x);
    tm.insert({x, --stk.end()});
  }

  int pop() {
    auto it = --stk.end();
    int ans = *it;
    auto mit = --tm.upper_bound(ans);
    tm.erase(mit);
    stk.erase(it);
    return ans;
  }

  int top() {
    return stk.back();
  }

  int peekMax() {
    return tm.rbegin()->first;
  }

  int popMax() {
    auto mit = --tm.end();
    auto it = mit->second;
    int ans = *it;
    tm.erase(mit);
    stk.erase(it);
    return ans;
  }

private:
  multimap<int, list<int>::iterator> tm;
  list<int> stk;
};

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack* obj = new MaxStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->peekMax();
 * int param_5 = obj->popMax();
 */