建立企业网站 优帮云,做欧美市场的网站,做照片有那些网站好,泛微oa办公系统官网目录 问题描述单个栈实现双栈实现不开辟额外空间 问题描述
设计一个支持 push #xff0c;pop #xff0c;top 操作#xff0c;并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop()… 目录 问题描述单个栈实现双栈实现不开辟额外空间 问题描述
设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。
示例 1: 输入 [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”] [[],[-2],[0],[-3],[],[],[],[]] 输出 [null,null,null,null,-3,null,0,-2]
解释 MinStack minStack new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); -- 返回 -3. minStack.pop(); minStack.top(); -- 返回 0. minStack.getMin(); -- 返回 -2.
单个栈实现
题目只是要求 在常数时间内检索到最小元素 对其他操作没有要求那么可以牺牲 pop() 操作的性能是一种可行的办法。
class MinStack:def __init__(self):self.stack []self.min float(inf)def push(self, val: int) - None:self.stack.append(val)if self.min val:self.min valdef pop(self) - None:s self.stack.pop()if self.stack:if s self.min:self.min min(self.stack)else:self.min float(inf)def top(self) - int:return self.stack[-1]def getMin(self) - int:return self.min
getMin() 方法的算法复杂度为 O ( 1 ) O(1) O(1) 如果做 n 次进栈出栈操作算法总的复杂度为 O ( N 2 ) O(N^2) O(N2)
双栈实现
进一步来说如果出栈的复杂度不想那么高的话可以使用一点额外空间来换取速度。 具体来说再维护一个最小栈顶部存储当前栈中元素的最小值。
class MinStack:def __init__(self):self.stack []self.min_stack []def push(self, val: int) - None:if not self.stack or self.getMin() val:self.min_stack.append(val)else:self.min_stack.append(self.getMin())self.stack.append(val)def pop(self) - None:self.stack.pop()self.min_stack.pop()def top(self) - int:return self.stack[-1]def getMin(self) - int:return self.min_stack[-1]
getMin() 方法的算法复杂度为 O ( 1 ) O(1) O(1) 如果做 n 次进栈出栈操作算法总的复杂度为 O ( N ) O(N) O(N)
不开辟额外空间
网上有人说他在面试的时候被要求不额外开辟空间下面列了我找到的答案。 相当于把 双栈实现 中的双栈合并为单个栈于是栈里存储最小值和当前值之间的差值。每一次出栈的时候通过这个插值还原出上一个时刻的最小值。
class MinStack:def __init__(self):initialize your data structure here.self.stack []self.min_value -1def push(self, x: int) - None:if not self.stack:self.stack.append(0)self.min_value xelse:diff x-self.min_valueself.stack.append(diff)self.min_value self.min_value if diff 0 else xdef pop(self) - None:if self.stack:diff self.stack.pop()if diff 0:top self.min_valueself.min_value top - diffelse:top self.min_value diffreturn topdef top(self) - int:return self.min_value if self.stack[-1] 0 else self.stack[-1] self.min_valuedef getMin(self) - int:return self.min_value if self.stack else -1
getMin() 方法的算法复杂度为 O ( 1 ) O(1) O(1) 如果做 n 次进栈出栈操作算法总的复杂度为 O ( N ) O(N) O(N)
