剑指 Offer 30. 包含min函数的栈

说明

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

示例

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.

题解思路

创建B来辅助A

代码实现

class MinStack: def __init__(self): """ initialize your data structure here. """ self.stack_A = [] self.stack_B = [] def push(self, x: int) -> None: self.stack_A.append(x) """将当前最小值存入B中，以便输出最小值""" if not self.stack_B or self.stack_B[-1] >= x: self.stack_B.append(x) def pop(self) -> None: """如果删除的最后一个元素与B中最后一个相等，需要把B中的最后一个也pop，否则会影响min的结果""" if self.stack_A.pop() == self.stack_B[-1]: self.stack_B.pop() def top(self) -> int: return self.stack_A[-1] def min(self) -> int: return self.stack_B[-1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.min()