一、题目描述

题目描述

二、思路

用双栈解决。一个栈st正常存取数据，另一个栈minst用以存当前最小元素（两个栈元素个数始终一样）。
push一个数时进行判断，若该数比当前最小元素还小，那么将其存入minst栈顶，否则将当前最小元素再次存入minst栈顶；
pop操作需要两个栈一起pop()。

三、代码

class MinStack {
public:
    stack<int> st;  // 用来存储元素
    stack<int> minst;  // 存储当前最小元素
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        st.push(x);
        if(minst.size() == 0){
            minst.push(x);  // 第一个元素，直接存入
        }else{
            int cur_min = minst.top();  // 当前最小元素
            if(x < cur_min){  // x比当前元素还小
                minst.push(x);  // 将当前最小元素x压入栈顶
            }else{
                minst.push(cur_min);  // 当前最小元素依然不变
            }
        }
    }
    
    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(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

四、提交结果

提交结果