静奢之境

LongDz 的数字文墨提案

155. 最小栈

3 min

题目

最小栈 中等

解法：双栈法

思路

核心思想是使用双栈：主栈存储元素，辅助栈同步存储当前最小值。

该方法正确的原因是：每次 push 时辅助栈记录 min(原最小值, 新值)，使其栈顶始终为当前栈的最小值；pop 时同步弹出，保持状态一致，因此 getMin 可直接返回辅助栈顶。

  • Step 1: 初始化 minst 栈，压入 INT_MAX 作为哨兵值
  • Step 2: push 时，主栈压入 val，辅助栈压入 min(minst.top(), val)
  • Step 3: pop 时，两个栈同时弹出栈顶元素
  • Step 4: top 操作返回主栈栈顶元素
  • Step 5: getMin 操作返回辅助栈栈顶元素

复杂度

  • 时间复杂度: O(1)O(1)
  • 空间复杂度: O(n)O(n)

代码

class MinStack {
public:
    stack<int>st;
    stack<int>minst;
    MinStack() {
        minst.push(INT_MAX);
    }
    
    void push(int val) {
        st.push(val);
        minst.push(min(minst.top(),val));
    }
    
    void pop() {
        st.pop();
        minst.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minst.top();
    }

class MinStack {
public:
    stack<int>st;
    stack<int>minst;
    MinStack() {
        minst.push(INT_MAX);
    }
    
    void push(int val) {
        st.push(val);
        minst.push(min(minst.top(),val));
    }
    
    void pop() {
        st.pop();
        minst.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minst.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
栈 设计 LeetCode