题目

设计一个支持 push，pop，top 操作，并能 在常数时间内检索到最小元素的栈。

  • push(x) — 将元素 x 推入栈中。
  • pop() — 删除栈顶的元素。
  • top() — 获取栈顶元素。
  • getMin() — 检索栈中的最小元素。

示例:

  1. MinStack minStack = new MinStack();
  2. minStack.push(-2);
  3. minStack.push(0);
  4. minStack.push(-3);
  5. minStack.getMin();   --> 返回 -3.
  6. minStack.pop();
  7. minStack.top();      --> 返回 0.
  8. minStack.getMin();   --> 返回 -2.

方案一

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self._deque = collections.deque()
        self._min_stack = []

    def push(self, x: int) -> None:
        self._deque.append(x)
        if len(self._min_stack) == 0 or x <= self._min_stack[-1]:
            self._min_stack.append(x)

    def pop(self) -> None:
        poped = self._deque.pop()
        if poped == self._min_stack[-1]:
            self._min_stack.pop()
        return poped

    def top(self) -> int:
        return self._deque[-1]

    def getMin(self) -> int:
        return self._min_stack[-1]