【解题思路】
普通栈的pop,push操作的时间复杂度为O(1),但通过遍历的方法找到最小元素的时间复杂度为O(n)。一般情况下可以采用空间换取时间的办法来降低时间复杂度,使用两个栈结构,一个栈用来存储数据,另一个栈用来存储最小元素。
例如
1.使用 elem 和 min 两个栈结构,elem 用来存储数据,min 用来存储 elem 栈的最小元素。
2.在入栈时,如果当前入栈的元素比原来栈中的最小值还小,则把这个值压入 min 栈中;
3.在出栈时,如果当前出栈的元素恰好为当前栈中的最小值,则 min 栈的栈顶元素也出栈,使得当前最小值变为其入栈之前的那个最小值。
class getStackMinEle:
def __init__(self):
self.elem = []
self.min = []
def push(self, e):
self.elem.append(e)
if (len(self.min) == 0):
self.min.append(e)
elif (e < self.min[-1]):
self.min.append(e)
def pop(self):
topdata = self.elem[-1]
self.elem.pop()
if (topdata == self.min[-1]):
self.min.pop()
def getMin(self):
if (len(self.min) == 0):
return "没有最小值"
else:
return (self.min[-1])
mystack=getStackMinEle()
mystack.push(6)
print('元素入栈后元素栈和最小值栈分别是')
print(mystack.elem)
print(mystack.min)
mystack.push(5)
print('元素入栈后元素栈和最小值栈分别是')
print(mystack.elem)
print(mystack.min)
mystack.push(7)
print('元素入栈后元素栈和最小值栈分别是')
print(mystack.elem)
print(mystack.min)
mystack.push(3)
print('元素入栈后元素栈和最小值栈分别是')
print(mystack.elem)
print(mystack.min)
mystack.pop()
print('元素出栈后元素栈和最小值栈分别是')
print(mystack.elem)
print(mystack.min)
mystack.pop()
print('元素出栈后元素栈和最小值栈分别是')
print(mystack.elem)
print(mystack.min)
欢迎大家转发,一起传播知识和正能量,帮助到更多人。辛苦大家转发时注明出处(也是咱们公益编程交流群的入口网址):http://liujingwei.cn