一个可以在O(1)时间内获取出最小值的栈。
| 54 | |
| 55 | |
| 56 | class MinStack(Stack): |
| 57 | """ |
| 58 | 一个可以在O(1)时间内获取出最小值的栈。 |
| 59 | """ |
| 60 | def __init__(self): |
| 61 | super().__init__() |
| 62 | |
| 63 | self.minStack = Stack() |
| 64 | |
| 65 | def push(self, value): |
| 66 | super().push(value) |
| 67 | if self.minStack.empty(): |
| 68 | self.minStack.push(value) |
| 69 | else: |
| 70 | if self.minStack.get_top() <= value: |
| 71 | self.minStack.push(self.minStack.get_top()) |
| 72 | else: |
| 73 | self.minStack.push(value) |
| 74 | |
| 75 | def pop(self): |
| 76 | super().pop() |
| 77 | self.minStack.pop() |
| 78 | |
| 79 | def get_min(self): |
| 80 | """ |
| 81 | 返回栈顶但不压出。 |
| 82 | """ |
| 83 | return self.minStack.get_top() |
| 84 | |
| 85 | |
| 86 | a = Stack() |