155. Min Stack

一般最簡單的做法

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
    }
    
    void push(int x) {
        stack.push_back(x);
    }
    
    void pop() {
        if(stack.empty()) return;
        stack.pop_back();
        
    }
    
    int top() {
       return  stack.back();
    }
    
    int getMin() {
        int min_value = INT_MAX;
        for(auto i: stack){
            min_value = min(i, min_value);
        }
        return min_value;
    }
    private:
        vector<int> stack;
      
       
};

但getmin的時間複雜度為O(n)

該如何收到O(1)呢

再多一個min vector, 來記錄當前最小的值, 因為一開始是空, 所以我們推一個INT_MAX

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        min_st.push_back(INT_MAX);
    }
    
    void push(int x) {
        stack.push_back(x);
        if(x <= min_st.back()){
            min_st.push_back(x);
        }
    }
    
    void pop() {
        if(stack.empty()) return;
        int t = stack.back();
        stack.pop_back();
        if(t == min_st.back()){
            min_st.pop_back();
        }
    }
    
    int top() {
       return  stack.back();
    }
    
    int getMin() {
        return min_st.back();
    }
    private:
        vector<int> stack;
        vector<int> min_st;
       
};