Leetcode题解剑指 Offer 30. 包含min函数的栈

PROBLEM

难度简单

MY ANSWER

两个栈，一个存放数据，一个存放前者对应的元素为栈顶时的最小值。

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

    }
    
    void push(int x) {
        s.push(x);
        if(m.empty()) {
            m.push(x);
            return;
        }
        if(x < m.top()) {
            m.push(x);
        }
        else {
            m.push(m.top());
        }
    }
    
    void pop() {
        s.pop();
        m.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int min() {
        return m.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->min();
 */

BETTER SOLUTION

也可只用一个栈实现，每次push和pop都把最小值和数据压栈进栈，用INT_MAX表示int的最大值。

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s;
    int m = INT_MAX;
    MinStack() {

    }
    
    void push(int x) {
        s.push(m);
        if(x < m) {
            m = x;
        }
        s.push(x);
    }
    
    void pop() {
        s.pop();
        m = s.top();
        s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int min() {
        return m;
    }
};

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

SUMMARY

注意使用辅助栈来实现对应的最小值，INT_MAX、INT_MIN表示int的最大最小值。