设计一个栈结构,满足min,push,pop操作的时间复杂度均为O(1)

【解题思路】


普通栈的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
 

上一篇:C语言实现链式栈(不带头结点)


下一篇:225. Implement Stack using Queues