今日题目(剑指Offer系列)
剑指 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.
解题思路:
>本道题考的是栈的使用, >题目中要求各个函数的复杂度为O(1) >push和pop可以满足,而min就不太行 >所以我们需要用另外一个栈来进行保存当前栈的最小元素 >为什么用栈存呢? >因为原来的栈需要不断添加或者弹出元素 >又因为栈具有先进后出的特性 >所以可以保存与原来的栈具有实时的交互,栈顶总是当前栈的最小值
Python解法:
class MinStack: def __init__(self): """ initialize your data structure here. """ self.A,self.B=[],[] def push(self, x: int) -> None: self.A.append(x) if not self.B or x<=self.B[-1]: self.B.append(x) def pop(self) -> None: if self.A[-1]==self.B[-1]: self.B.pop() self.A.pop() def top(self) -> int: return self.A[-1] def min(self) -> int: return self.B[-1]
Java解法:
class MinStack { Stack<Integer> A,B; /** initialize your data structure here. */ public MinStack() { A=new Stack<>(); B=new Stack<>(); } public void push(int x) { A.push(x); if(B.empty()||x<=B.peek()){ B.push(x); } } public void pop() { if(A.peek().equals(B.peek())){ B.pop(); } A.pop(); } public int top() { return A.peek(); } public int min() { return B.peek(); } }