最小栈

[编程题]最小栈

热度指数：5595 时间限制：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

算法知识视频讲解

牛客题解官

发表于 2020-06-05 18:51:57

题解：考察点：栈易错点：本题要求、、三种操作都在复杂度内完成，也就是说都必须在常数时间内完成，其中和都是栈本来的操作，很多同学会考虑使用堆来维护最小值，但是这是不对的，因为堆每次找最小值的时间复杂度为题解：可以考虑使用两个栈来共同维护，一个栈用来进行元素常规的出栈和入栈操作，另一个栈维护展开全文

牛客第一菜狗

发表于 2021-05-22 01:35:03

可以不使用线性的额外空间，只需要O(1)的额外空间复杂度：· 记录minx，表示当前最小值。push(x)时，判断x是否大于minx。· 使用栈s，push的不是原始插入值，而是差值：x-minx。若x>=minx，则皆大欢喜，直接push(x-minx)，不需要修改minx。对应的pop 展开全文