AcWing
  • 首页
  • 题库
  • 题解
    • LeetCode
    • AcWing
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 41. 包含min函数的栈(仅使用一个栈)    原题链接    简单

作者: 作者的头像   wzc1995 ,  2019-12-03 01:29:38 ,  阅读 28


3


算法

(栈) $O(n)$
  1. 两个栈的方法已经烂大街了,这里提供仅用一个栈的方法。
  2. 我们只开一个普通栈和一个变量 min_value 记录最小值。栈中存放当前元素与当前最小值的差值。
  3. 进栈时,如果栈为空,则插入当前元素,然后更新 min_value。如果栈不空,则插入 x - min_value,然后更新 min_value。
  4. 出栈时,如果栈顶元素小于 0,则说明栈顶元素为当前最小值,需要回滚上一次的最小值。出栈。
  5. 取栈顶元素时,如果栈中只有一个元素,直接返回。否则,如果栈顶元素大于 0,则说明栈顶不是当前最小值,通过差值计算找到最小值;如果栈顶元素小于 0,则直接返回最小值。
  6. 返回最小值时,直接返回 min_value。
  7. 注意,整数运算有可能溢出,需要用 long long。

时间复杂度

  • 每个操作的时间复杂度都是常数。

空间复杂度

  • 仅使用一个栈和普通变量。

C++ 代码

class MinStack {
public:
    /** initialize your data structure here. */
    #define LL long long
    stack<LL> st;
    LL min_value;

    MinStack() {

    }

    void push(int x) {
        if (st.empty()) {
            st.push(x);
            min_value = x;
        } else {
            st.push(x - min_value);
            min_value = min(min_value, (LL)(x));
        }
    }

    void pop() {
        if (st.top() < 0)
            min_value -= st.top();

        st.pop();
    }

    int top() {
        if (st.size() == 1)
            return st.top();
        else if (st.top() > 0)
            return min_value + st.top();
        else
            return min_value;
    }

    int getMin() {
        return min_value;
    }
};

/**
 * 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();
 */

评论列表:


用户头像
佩头奇   6天前     回复

如果pop刚好是min_value,回滚上一次的最小值, 怎么理解 min_value -= st.top();

用户头像
wzc1995   6天前     回复

top 刚好是最小值,则 top 存的就是 0。


用户头像
佩头奇   7天前     回复

学习了

你确定删除吗?

© 2018-2019 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息