设计getMin功能的栈

[编程题]设计getMin功能的栈

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

实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

输入描述:

第一行输入一个整数N，表示对栈进行的操作总数。

下面N行每行输入一个字符串S，表示操作的种类。

如果S为"push"，则后面还有一个整数X表示向栈里压入整数X。

如果S为"pop"，则表示弹出栈顶操作。

如果S为"getMin"，则表示询问当前栈中的最小元素是多少。

输出描述:

对于每个getMin操作，输出一行表示当前栈中的最小元素是多少。

示例1

输入

6
push 3
push 2
push 1
getMin
pop
getMin

输出

1
2

备注:

1<=N<=1000000

-1000000<=X<=1000000

数据保证没有不合法的操作

算法知识视频讲解

Python3

Pandazdy

list1 = []
a = int(input())
count = 0
while count < a:
    count += 1
    b = input()
    if 'push' in b:
        list1.append(b.split(' ')[1])
    elif 'pop' in b:
        list1.pop(-1)
    elif 'getMin' in b:
        print(min(map(int,list1)))

发表于 2022-04-28 00:14:46 回复(0)

Python3

毓毓子最可爱

#利用两个栈实现
#一个是保存所有数据的栈
#另外一个是保存到现在为止所有数据中最小值的栈
#用python中的list模拟栈
#普通存放数据的栈
normal_stack=[]
#存放最小元素的栈
min_stack=[]
#获取输入
#input()表示从控制台获得一个输入，返回的是字符串形式
#需要转化为int类型
n=int(input())
#模拟，进行栈的操作
#共操作了n次
for i in range(n):
    #获取操作命令和数字（如果有）
    operator=input()
    #判断操作类型
    if operator[:2]=='pu':
        #分割出要保存的数字
        #.split()代表用空格分割字符串
        _,number=operator.split()
        number=int(number)
        normal_stack.append(number)
        #更新最小栈
        #如果当前存放最小值的栈为空
        if len(min_stack)==0:
            #直接压入
            min_stack.append(number)
        #否则的话
        #如果当前元素小于栈顶元素，压入
        else:
            #等于是允许最小值重复出现
            if number<=min_stack[-1]:
                min_stack.append(number)
    if operator[:2]=='ge':
        print(min_stack[-1])
    if operator[:2]=='po':
        #list中的pop方法默认弹出最后一个元素
        pop_num=normal_stack.pop()
        #如果弹出的是最小值，最小值栈也要更新
        if pop_num==min_stack[-1]:
            min_stack.pop()

发表于 2021-08-21 16:28:22 回复(0)