《剑指offer》刷题系列——（十八）包含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.

思路

要实现时间复杂度为O(1)，就要借助辅助空间来牺牲空间复杂度。 我们要实现的min函数，不仅要能返回一个原始栈中所有元素的最小值，还要能实现，当原始栈中最小元素被弹出后，我们还能找到剩下元素的最小值（次小元素），所以如果能将原始栈每次更新后的元素的最小值都保存下来就很容易找到。 定义一个空的原始栈stack1和一个空的辅助栈stack2。 下面是操作过程。 每一次在stack1中压入新的元素x时，如果x小于stack2栈顶的元素，则将x也压入stack2，否则stack2不进行操作。 每一次从stack1中弹出元素时，如果stack1的栈顶元素也存在于stack2中，那么stack2也要进行弹出操作。

代码

class MinStack: def __init__(self): """ initialize your data structure here. """ self.stack1,self.stack2 = [],[] def push(self, x: int) -> None: self.stack1.append(x) if not self.stack2 or x <= self.stack2[-1]: self.stack2.append(x) def pop(self) -> None: if self.stack1[-1]==self.stack2[-1]: self.stack2.pop() self.stack1.pop() def top(self) -> int: return self.stack1[-1] def min(self) -> int: return self.stack2[-1]