云浮各类免费建站,商业街网站建设方案,网站seo诊断报告,广州三合一企业网站哪家好设计一个支持 push #xff0c;pop #xff0c;top 操作#xff0c;并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int get…设计一个支持 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.提示
-231 val 231 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 104 次
1. 分析
题目要求实现 MinStack 类且在常数时间内检索到最小元素的栈。关键是如何实现常数时间内检索如果用普通的min()函数对于栈内所有元素排序的话时间复杂度是nlongn(内置快排实现)。我们可以尝试往栈里面存一个列表列表里面存元组然后依次更新最小值和入栈元素,本质还是用到了空间换时间的方法。
2. 实现思路
栈用python实现就较易先把栈stack[]定义成一个列表List,在python中,stack.pop()就是移除列表的最后一个元素类似出栈操作。有元素入栈的时候我们往列表里面存一个元组x,最小值每次存的时候就会更新这个最小值但是原来的值也也还是相当于数组是不断的增加元素就算删除一个元素之前的最小值依然存在。如图 我们先push4由于是空栈添加元素需要特殊处理stack.append((x,x)因为空栈时入栈入栈元素即为最小值若非空栈是元素入栈则往列表里面添加当前值和与上一个最小值的最小值这样可以防止在pop()后之前得到到元素依然是最小值。
3. 代码如下
class MinStack(object):def __init__(self):self.stack[]def push(self, x):if not self.stack:self.stack.append((x,x))#第一个x存栈的元素第二个存此时的最小值else:self.stack.append((x,min(x,self.stack[-1][1])))def pop(self):self.stack.pop()def top(self):return self.stack[-1][0]def getMin(self):return self.stack[-1][1]obj MinStack()
obj.push(4)
print(obj.stack)
obj.push(3)
print(obj.stack)
obj.push(5)
print(obj.stack)
obj.push(1)
print(obj.stack)
obj.pop()
print(obj.stack)
obj.pop()
print(obj.stack)
print(obj.getMin())
# param_3 obj.top()
# param_4 obj.getMin()
stack[-1]是取出stack的最后一个元素
