LeetCode 155 - 最小栈 - [数组模拟栈]

题目链接：https://leetcode-cn.com/problems/min-stack/description/

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

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

题解：

以往，我们经常用 $min[i]$ 维护区间 $[1,i]$ 的最小值，在这里我们同样也可以这么做。

AC代码（要想超过百分百的cpp提交记录，关闭IO同步是必不可少的……）：

static const auto io_sync_off = []()

{

    // turn off sync

    std::ios::sync_with_stdio(false);

    // untie in/out streams

    std::cin.tie(nullptr);

    return nullptr;

}();

#define maxn 10000

struct MinStack

{

    int s[maxn],mn[maxn],tot;

    MinStack() {

        tot=;

    }

    void push(int x) {

        s[tot]=x;

        if(tot) mn[tot]=min(mn[tot-],x);

        else mn[tot]=x;

        tot++;

    }

    void pop() {

        tot--;

    }

    int top() {

        return s[tot-];

    }

    int getMin() {

        return mn[tot-];

    }

};

巴特西

LeetCode 155 - 最小栈 - [数组模拟栈]

最新文章

热门文章