栈

方法一

建立一个辅助栈，栈顶保存到当前元素的最小值

参考代码

  1. class MinStack:
  3.     def __init__(self):
  4.         """
  5.         initialize your data structure here.
  6.         """
  7.         self.s = []
  8.         self.s_min = [math.inf]
  11.     def push(self, x: int) -> None:
  12.         self.s.append(x)
  13.         self.s_min.append(min(self.min(),x))
  16.     def pop(self) -> None:
  17.         self.s.pop()
  18.         self.s_min.pop()
  21.     def top(self) -> int:
  22.         return self.s[-1]
  24.     def min(self) -> int:
  25.         return self.s_min[-1]
  29. # Your MinStack object will be instantiated and called as such:
  30. # obj = MinStack()
  31. # obj.push(x)
  32. # obj.pop()
  33. # param_3 = obj.top()
  34. # param_4 = obj.min()

复杂度分析

时间复杂度O(n)
空间复杂度O(1)