155. Min Stack

155. Min Stack

抄的dicussion中的一种实现方法，真的帅

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        topEle = nullptr;
    }    
    void push(int val) {
        if(!topEle)
            topEle = new Node(val, val);
        else
            topEle = new Node(val, min(topEle->min, val), topEle);
    }
    
    void pop() {
        auto tmp = topEle;
        topEle = tmp->next;
        delete tmp;
    }
    
    int top() {
        return topEle->val;
    }
    
    int getMin() {
        return topEle->min;
    }
private:
    struct Node {
        int val;
        int min;
        Node* next;
        Node () : val(0), min(INT_MAX), next(nullptr) {}
        Node (int val, int min) : val(val), min(min), next(nullptr) {}
        Node (int val, int min, Node* next) : val(val), min(min), next(next) {}
    };
    Node* topEle;
};

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

使用两个栈

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {
        values.push(x);
        if(minValues.empty() || x <= minValues.top())
            minValues.push(x);
    }
    
    void pop() {
        if(minValues.top() == values.top())
            minValues.pop();
        values.pop();
    }
    
    int top() {
        return values.top();
    }
    
    int getMin() {
        return minValues.top();
    }
private:
    stack<int> values;
    stack<int> minValues;
};

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