题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

思路

创建一个辅助栈，用于存储每次push后的最小值，同时在pop后更新辅助栈中的最小值。

代码

  1. class MinStack:
  3.     def __init__(self):
  4.         """
  5.         initialize your data structure here.
  6.         """
  7.         self.stack = [] # 数据栈
  8.         self.min_stack = [] # 不断把最小元素压入最小栈中
  10.     def push(self, x: int) -> None:
  11.         self.stack.append(x)
  12.         if not self.min_stack or self.min_stack[-1] >= x:
  13.             self.min_stack.append(x)
  15.     def pop(self) -> None:
  16.         if self.stack.pop() == self.min_stack[-1]:
  17.             self.min_stack.pop()
  19.     def top(self) -> int:
  20.         return self.stack[-1]
  23.     def min(self) -> int:
  24.         return self.min_stack[-1]
  28. # Your MinStack object will be instantiated and called as such:
  29. # obj = MinStack()
  30. # obj.push(x)
  31. # obj.pop()
  32. # param_3 = obj.top()
  33. # param_4 = obj.min()

进一步优化，不用每次都把最小值入最小栈，只需要比较当前stack中的栈顶元素和最小值，如果大于最小值，则最小值所在的栈就不用出栈。

  1. class MinStack:
  3.     def __init__(self):
  4.         """
  5.         initialize your data structure here.
  6.         """
  7.         self.stack = []
  8.         self.stackMin = []
  10.     def push(self, x: int) -> None:
  11.         self.stack.append(x)
  12.         if not self.stackMin or x <= self.stackMin[-1]:
  13.             self.stackMin.append(x)
  16.     def pop(self) -> None:
  17.         if self.top() == self.stackMin[-1]:
  18.             self.stackMin.pop()
  19.         self.stack.pop()
  23.     def top(self) -> int:
  24.         return self.stack[-1]
  27.     def min(self) -> int:
  28.         return self.stackMin[-1]