[LeetCode] 0155. Min Stack 最小栈 & C++Runtime加速

题目

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.

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。

Example:

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin();   --> Returns -3.

minStack.pop();

minStack.top();      --> Returns 0.

minStack.getMin();   --> Returns -2.

解法一

用两个栈就完事了，值得一说的是加速代码，暂时没找到什么空间复杂度很低的算法。

参考资料：https://blog.csdn.net/yujuan_mao/article/details/8119529

取消标准输入输出的同步，可以加速输入三倍（因为cin太慢啦），关掉cin和stdin的同步后，再把cin和cout的绑定也取消掉。瞬间提速……

static int x = [](){

    std::ios::sync_with_stdio(false);

    std::cin.tie(NULL);

    std::cout.tie(NULL);

    return NULL;

}();

class MinStack {

private:

    stack<int> data;

    stack<int> min_stack;

public:

    /** initialize your data structure here. */

    MinStack() = default;

    void push(int x) {

        data.push(x);

        if (min_stack.empty() || min_stack.top() >= x) {

            min_stack.push(x);

        }

    }

    void pop() {

        if (data.top() == min_stack.top()) {

            min_stack.pop();

        }

        data.pop();

    }

    int top() {

        return data.top();

    }

    int getMin() {

        return min_stack.top();

    }

};

运行结果

Runtime: 28 ms, faster than 98.82% of C++ online submissions for Min Stack.

Memory Usage: 17.2 MB, less than 12.90% of C++ online submissions for Min Stack.

巴特西

[LeetCode] 0155. Min Stack 最小栈 & C++Runtime加速

题目

解法一

最新文章

热门文章