题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/

题解

辅助栈

由于栈先进后出的特性，当进入一个值是当前最小值时，假设后面进来的数都没它小，那在它出来之前，返回的最小值都是这个数。

我们可以用一个另外的栈存最小值，每进来一个数，就在这个最小值的辅助栈中存入当前最小值，以表示当前值为栈顶时应该被查询到的最小值。

也就是说，入栈时，对最小值的栈，如果入栈元素比栈顶元素小，那么将入栈元素入栈，否则将栈顶重复入栈。两个栈同进同出。

class MinStack {
    stack<int> stk, min_stk;
public:
    /** initialize your data structure here. */
    MinStack() {
        min_stk.push(INT_MAX);      // 方便栈为空时进行比较 
    }
    
    void push(int x) {
        stk.push(x);
        min_stk.push(::min(min_stk.top(), x));
    }
    
    void pop() {
        stk.pop();
        min_stk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int min() {
        return min_stk.top();
    }
};

调用 push、pop、top、min 的时间复杂度都是 O(1)；辅助栈额外空间 O(n)

保存差值

只需要维护当前状态的最小值，栈中存入差值，要注意最小值的更新和回退。

class MinStack {
    stack<long long> diff_stack;
    // 入栈可能更新最小值、出栈可能回退最小值，总是当前状态的最小值
    long long min_num;
public:
    /** initialize your data structure here. */
    MinStack() {}
    
    void push(int x) {
        if (diff_stack.empty()) {
            diff_stack.push(0);
            min_num = x;
        } else {
            // 先根据当前值计算差值入栈，如果入栈值 < 0，则说明这里更新了 min_num
            diff_stack.push(x - min_num);
            // 再更新最小值，这样出栈时如果栈顶元素 < 0，需要回退上一个最小值
            min_num = ::min(min_num, (long long)x);
        }
    }
    
    void pop() {
        if (diff_stack.empty()) return;
        if (diff_stack.top() < 0) {                 // 此时 min_num 即为当时入栈的 x
            min_num = min_num - diff_stack.top();   // pre_min_num = x(min_num) - diff_stack.top()
        }
        diff_stack.pop();
    }
    
    int top() {
        if (diff_stack.empty()) return 0;
        if (diff_stack.top() <= 0) return min_num;  // 此时 min_num 即为当时入栈的 x
        return diff_stack.top() + min_num;
    }
    
    int min() {
        return min_num;
    }
};

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