本文共 1585 字,大约阅读时间需要 5 分钟。
普通栈的 push() 和 pop() 函数的复杂度为 O(1) ;而获取栈最小值 min() 函数需要遍历整个栈,复杂度为 O(N) 。
【本题难点】 将 min() 函数复杂度降为 O(1) ,可通过建立辅助栈实现;
因此,只需设法维护好 栈 B 的元素,使其保持非严格降序,即可实现 min() 函数的 O(1) 复杂度。
push(x) 函数: 重点为保持栈 B 的元素是 非严格降序 的。
pop() 函数: 重点为保持栈 A, B的 元素一致性 。
top() 函数: 直接返回栈 A 的栈顶元素即可,即返回 A.peek() 。
min() 函数: 直接返回栈 B 的栈顶元素即可,即返回 B.peek() 。
class MinStack(object): def __init__(self): """ initialize your data structure here. """ self.A,self.B = [],[] def push(self, x): # 压入栈A, 压入栈B(当B为空 或 x小于栈B的栈顶元素时) self.A.append(x) if not self.B or self.B[-1]>=x: self.B.append(x) def pop(self): # A出栈, B出栈(若A弹出的 即为 B的栈顶元素) if self.A.pop() == self.B[-1]: self.B.pop() def top(self): return self.A[-1] # 直接返回栈 A 的栈顶元素即可 def min(self): return self.B[-1] # 直接返回栈 B 的栈顶元素即可# 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()'''作者:jyd链接:https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/'''
转载地址:http://tfjii.baihongyu.com/