動機

複習minstk

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

 

Example 1:

Input[MinStack,push,push,push,getMin,pop,top,getMin][[],[-2],[0],[-3],[],[],[],[]]Output[null,null,null,null,-3,null,0,-2]ExplanationMinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); // return -3minStack.pop();minStack.top();    // return 0minStack.getMin(); // return -2

 

Constraints:

  • -231 <= val <= 231 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 104 calls will be made to push, pop, top, and getMin.

Sol

stk同時放目前最小值

class MinStack:
    def __init__(self):
        self.stk = []

    def push(self, val: int) -> None:
        if not self.stk:
            self.stk.append([val,val])
        else:
            self.stk.append([val, val if val < self.getMin() else self.getMin()])

    def pop(self) -> None:
        self.stk.pop()

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

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