最小栈

[编程题]最小栈

热度指数：5633 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

实现一个最小栈，有三种操作，min：得到栈中的最小值，push：在栈顶插入一个元素，pop：弹出栈顶元素，使这三种操作的时间复杂度都是O(1)
要求：语言不限

输入描述:

第一行是一个数Q，接下来Q行每行表示一个操作，每行首先是操作op
若op==0,则输出当前栈中的最小值；
若op==1，表示push，接着正整数x，把在x放进栈顶；
若op==2，表示pop，弹出栈顶元素
保证Q<=500000,保证op==0或2时（即min操作和pop操作时）栈不为空。
你可以假设一开始栈的空的。

输出描述:

对应每个op==0或2，如果是op==0输出当前栈中的最小值，如果是op==2输出弹出的元素。

示例1

输入

输出

说明

第一个操作为push 3,此时栈元素为3
第二个操作为push 4,此时栈元素为3,4
第三个操作为min,此时栈元素为3,4，输出最小值3
第四个操作为push 2,此时栈元素为3,4,2
第五个操作为min,此时栈元素为3,4,2，输出最小值2
第六个操作为pop,弹出元素2，此时栈元素为3,4，输出弹出的元素2
第七个操作为min,此时栈元素为3,4，输出最小值3

算法知识视频讲解

Python

贾志统

class MyStack:
    def __init__(self):
        self.st_data = []
        self.st_min = []
    
    def push(self, node):
        self.st_data.append(node)
        if not self.st_min or node < self.st_min[-1]:
            self.st_min.append(node)
        else:
            self.st_min.append(self.st_min[-1])
    
    def pop(self):
        self.st_min.pop()
        return self.st_data.pop()
    
    def get_min(self):
        return self.st_min[-1]


st = MyStack()
Q = input()
for i in range(Q):
    #lst = input().split()
    #op = int(lst[0])
    op = raw_input()
    if op == "0":
        print(st.get_min())
    elif op == "2":
        print(st.pop())
    else:
        st.push(int(op[2:]))

发表于 2019-09-06 20:48:17 回复(0)