下面是错误答案。有待以后调试，不舍得放弃，留了下来：

数组模拟栈。入栈时直接统计最小值并放入数组

class MinStack {

public:

    MinStack()

    {

        arr.resize(100000);//多么痛的领悟

        minarr.resize(100000);

        ntop=-1;

    }

    void push(int x) {

        ++ntop;

        arr[ntop]=x;

        if(ntop==0)

            minum=INT_MAX;

        if(x<=minum)

            minum=x;

        minarr[ntop]=minum;

    }

    void pop() {

        minarr[ntop]=0;

        ntop--;

    }

    int top() {

        return arr[ntop];

    }

    int getMin() {

        return minarr[ntop];

    }

private:

    vector<int> arr;

    vector<int> minarr;

    int ntop;

    int minum;

};

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">

调试分析代码后已AC：

数组模拟栈

在压栈的时候，直接统计出当前最小值minum放入数组

出栈时，更新当前最小值minum（第一次忘了）~

class MinStack {

public:

    MinStack()

    {

        arr.resize(100000);//多么痛的领悟

        minarr.resize(100000);

        ntop=-1;

    }

    void push(int x) {

        arr[++ntop]=x;

        if(ntop==0)

            minum=INT_MAX;

        if(x<=minum)

            minum=x;

        minarr[ntop]=minum;

    }

    void pop() {

        minarr[ntop]=0;

        ntop--;

        minum=minarr[ntop];//上面的代码缺少这一行

    }

    int top() {

        return arr[ntop];

    }

    int getMin() {

        return minarr[ntop];

    }

private:

    vector<int> arr;

    vector<int> minarr;

    int ntop;

    int minum;

};

学习别人家的算法设计：

他这样处理事实上还是在压栈时就获取了最小值。

相较普通的栈。题目要求多实现一个操作getMin(): 获取栈中最小的元素

我们维护两个栈：一个栈是普通栈s保存全部元素, 还有一个栈是最小栈mins保存s中的“曾出现过”的最小元素的递减序列。mins.top()即为getMin()的返回值。标识普通栈s里的最小元素。

考虑压栈 3 4 5 2 3 1, 它们有例如以下表现：

push   3 4 5 2 3 1

s      3 4 5 2 3 1

mins   3    2   1

亦即，当push(x)的x < mins.top()时，我们将x压入mins中。

大家能够发现。在上述push操作的随意间隔加我们若调用getMin()函数，mins.top()即为所求。

接下来考虑pop()操作，当且仅当s.top() == mins.top()时，我们才弹出mins的元素。这样就能够维护mins.top()始终为当前s里的最小值的性质。

class MinStack

{

public:

    void push(int x)

    {

        s.push(x);

        if (mins.empty() || x <= mins.top() )

            mins.push(x);

    }  

    void pop()

    {

        if (mins.top() == s.top())

        {

            s.pop();

            mins.pop();

        } else  {

            s.pop();

        }

    }  

    int top()

    {

        return s.top();

    }  

    int getMin()

    {

        return mins.top();

    }  

private:

    stack<int> s;

    stack<int> mins;

};  

注：本博文为EbowTang原创，兴许可能继续更新本文。假设转载，请务必复制本条信息！

原文地址：http://blog.csdn.net/ebowtang/article/details/50489486

原作者博客：http://blog.csdn.net/ebowtang

參考资源：

【1】网友。stephen_wong，博文地址。http://blog.csdn.net/stephen_wong/article/details/43924519