首页 > 代码库 > 011实现一个栈，除了push和pop操作，还要实现min函数以返回栈中的最小值,时间复杂度都为O(1)(keep it up)
011实现一个栈，除了push和pop操作，还要实现min函数以返回栈中的最小值,时间复杂度都为O(1)(keep it up)
实现一个栈，除了push和pop操作，还要实现min函数以返回栈中的最小值。
push，pop和min函数的时间复杂度都为O(1)。
看到这个题目最直接的反应是用一个变量来保存当前栈的最小值，让我们来看看这样可行否？
如果栈一直push那是没有问题，入栈元素如果比当前最小值还小，那就更新当前最小值。
可是如果pop掉的栈顶元素就是最小值，那么我们如何更新最小值呢？显然不太好办。
既然只用一个变量没法解决这个问题，那我们就增加变量。如果说每个结点除了保存当前的 值，
另外再保存一个从该结点到栈底的结点中的最小值。那么，不论哪个结点成为了栈顶结 点，
我们都有办法取得剩下的这些元素的最小值。代价是付出的空间多了一倍。代码不写了。
下面在介绍一种方法，我们可以在用一个栈来保存栈的最小值：
比如有一组数要入栈： 10 11 6 2 12
栈S1： 10 11 6 2 12
栈S2： 10 6 2
即到栈顶12时，最小值是2， 如果S1栈12出，和S2.top比较，如果大于S2.top，则S2不做
任何操作，如果等于S2.top， 则S2.pop（）； 比如S1的2出栈时，2 == S2.top(), 然后S2.pop();
这样就节省了很多空间。
但是上述方法还有问题：
比如数据
S1：10 11 6 2 2 2 12 这时
S2：10 11 6 2
当S1中2出栈时，S2中的2也会出栈，这样我们才去S1的最小值时就是6，明显错了。解决方法就是
push，pop和min函数的时间复杂度都为O(1)。
看到这个题目最直接的反应是用一个变量来保存当前栈的最小值，让我们来看看这样可行否？
如果栈一直push那是没有问题，入栈元素如果比当前最小值还小，那就更新当前最小值。
可是如果pop掉的栈顶元素就是最小值，那么我们如何更新最小值呢？显然不太好办。
既然只用一个变量没法解决这个问题，那我们就增加变量。如果说每个结点除了保存当前的 值，
另外再保存一个从该结点到栈底的结点中的最小值。那么，不论哪个结点成为了栈顶结 点，
我们都有办法取得剩下的这些元素的最小值。代价是付出的空间多了一倍。代码不写了。
下面在介绍一种方法，我们可以在用一个栈来保存栈的最小值：
比如有一组数要入栈： 10 11 6 2 12
栈S1： 10 11 6 2 12
栈S2： 10 6 2
即到栈顶12时，最小值是2， 如果S1栈12出，和S2.top比较，如果大于S2.top，则S2不做
任何操作，如果等于S2.top， 则S2.pop（）； 比如S1的2出栈时，2 == S2.top(), 然后S2.pop();
这样就节省了很多空间。
但是上述方法还有问题：
比如数据
S1：10 11 6 2 2 2 12 这时
S2：10 11 6 2
当S1中2出栈时，S2中的2也会出栈，这样我们才去S1的最小值时就是6，明显错了。解决方法就是
S2中每个元素添加一个计数器。这样当连续3次2出栈，S2中的2才出栈。
#include <iostream>
#include <stack>
struct DataCount
{
int data;
int count;
DataCount(int vData = http://www.mamicode.com/std::numeric_limits::infinity()) : data(vData), count(0) {}>
011实现一个栈，除了push和pop操作，还要实现min函数以返回栈中的最小值,时间复杂度都为O(1)(keep it up)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。