LeetCode 155. Min Stack    原题链接    简单

作者： 作者的头像   yxc ,  2018-05-31 23:35:05 ,  所有人可见 ,  阅读 3519

6


2

题目描述

请设计一个栈结构，支持 push、pop、top以及getMin操作，且每个操作的时间复杂度都是 $O(1)$。

  • push(x) – 向栈中压入元素 $x$；
  • pop() – 删除栈顶元素；
  • top() – 返回栈顶元素；
  • getMin() – 返回栈中的最小元素；

样例

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

算法

(单调栈) $O(1)$

我们除了维护基本的栈结构之外，还需要维护一个单调栈，来实现返回最小值的操作。
下面介绍如何维护单调栈：

  • 当我们向栈中压入一个数时，如果该数 $\le$ 单调栈的栈顶元素，则将该数同时压入单调栈中；否则，不压入，这是由于栈具有先进后出性质，所以在该数被弹出之前，栈中一直存在一个数比该数小，所以该数一定不会被当做最小数输出。
  • 当我们从栈中弹出一个数时，如果该数等于单调栈的栈顶元素，则同时将单调栈的栈顶元素弹出。
  • 单调栈的栈顶元素，就是当前栈中的最小数。

时间复杂度分析：四种操作都只有常数次入栈出栈操作，所以时间复杂度都是 $O(1)$.

C++ 代码

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stackValue;
    stack<int> stackMin;
    MinStack() {

    }

    void push(int x) {
        stackValue.push(x);
        if (stackMin.empty() || stackMin.top() >= x)
            stackMin.push(x);
    }

    void pop() {
        if (stackMin.top() == stackValue.top()) stackMin.pop();
        stackValue.pop();
    }

    int top() {
        return stackValue.top();
    }

    int getMin() {
        return stackMin.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

3 评论

用户头像
有心人   2021-08-15 21:29      1    踩      回复

不容易出错 的 同步 双栈法：

// 同步 双栈法：时间O(1), 空间O(n). 24ms, 15.9MB
class MinStack {
public:
    stack<int> s;
    stack<int> m; // 辅助栈, 比 s 多一个元素
    // m.push(INT_MAX); // 在这加 会报错

    /** initialize your data structure here. */
    MinStack() {
        m.push(INT_MAX); // 辅助栈初始存入 INT_MAX
    }

    void push(int val) {
        s.push(val);
        m.push(min(val, m.top()));
    }

    void pop() {
        s.pop();
        m.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return m.top();
    }
};
用户头像
小雨   2018-08-18 04:28         踩      回复

我每次刷题总是做不到bug free. 写这个的时候push 的时候忘记check minstack 是否为空， pop 的时候忘记check minstack 是否不为空， 还有当新存进去的vlaue 跟 minstack 栈顶元素一样大的时候也忘了 minstack也要再push 一个值，一开始还以为只有新进来的值比　minstack 　栈顶元素小的时候才需要push 到 minstack 呢

用户头像
yxc   2018-08-18 13:42      1    踩      回复

这道题目的细节挺多的，写的时候比较容易出错。
等写熟练之后这些问题就比较容易避免了hh。