【原创】leetCodeOj --- Min Stack 解题报告

题目地址：

https://oj.leetcode.com/problems/min-stack/

题目内容：

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

方法：

思路很简单。

维护两个栈，一个是数据栈正常进出；另一个最小栈的栈顶保存着当前数据栈中的最小值。

这么说可能看不太懂，举个例子吧。

数据栈中：9,9,3,4,4,4,5,3,3,10 其中10是栈顶。

最小栈中：9,9,3,3,3

push操作：

当前进入数据栈中的值小于等于最小栈栈顶的值的话，则也将该值压进最小栈，否则就只push数据栈。

pop操作：

如果当前数据栈栈顶的值等于最小栈栈顶的值，那么两个栈都弹值；否则只弹数据栈栈顶的值。

注意：C++中，如果使用vector，就会出现MLE错误。我换成stack就顺利过关。怀疑跟stack底层是个链表，而vector底层是动态增长数组有关。（剖析STL没看，SHIT，瞎猜一个）

全部AC代码：

class MinStack {

private:

    stack<int> trueStk;

    stack<int> minStk;

public:

    void push(int x) {

        trueStk.push(x);

        if (minStk.size() == )

            minStk.push(x);

        else

        {

            int tmp = getMin();

            if (x <= tmp)

                minStk.push(x);

        }

    }

    void pop() {

        int tmp = top();

        trueStk.pop();

        if (tmp == getMin())

            minStk.pop();

    }

    int top() {

        return trueStk.top();

    }

    int getMin() {

        return minStk.top();

    }

};

巴特西

【原创】leetCodeOj --- Min Stack 解题报告

最新文章

热门文章