题目

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

1.pop、push、getMin操作的时间复杂度都是O（1）。2.设计的栈类型可以使用现成的栈结构。

解答

使用一个栈保存每次入栈的元素；使用一个辅助栈保存当前栈的最小元素。

当push一个元素x时，考虑：

  • 如果辅助栈为空，那么将该元素x压入辅助栈；
  • 如果辅助栈不为空，比较辅助栈栈顶元素和当前元素x，如果x小于等于栈顶元素，则将该元素压入辅助栈

当pop一个元素x时，考虑：

  • 如果辅助栈 栈顶元素 < x，则当前最小值依然不变，不更新辅助栈；
  • 如果辅助栈 栈顶元素 == x，则说明当前最小值已经弹出，需要更新辅助栈。

image.png

代码

  1. class MinStack:
  3.     def __init__(self):
  4.         """
  5.         initialize your data structure here.
  6.         """
  7.         self.stack = []
  8.         self.auxStack = []
  11.     def push(self, x: int) -> None:
  12.         if not self.stack or x <= self.auxStack[-1]:
  13.             self.auxStack.append(x)
  15.         self.stack.append(x)
  18.     def pop(self) -> None:
  19.         if self.stack.pop() == self.auxStack[-1]:
  20.             self.auxStack.pop()
  23.     def top(self) -> int:
  24.         return self.stack[-1]
  27.     def min(self) -> int:
  28.         return self.auxStack[-1]
  32. # Your MinStack object will be instantiated and called as such:
  33. # obj = MinStack()
  34. # obj.push(x)
  35. # obj.pop()
  36. # param_3 = obj.top()
  37. # param_4 = obj.min()