155. Min Stack.md

题目

Min Stack

思路

500ms 5.67%

用向量模拟stack，并每次搜索最小值。

改进一： 用另一个数组存储到每个位置为止的最小值。

44ms 74.42%

代码

class MinStack {
public:
    MinStack() {}
    
    void push(int x) {
        c.push_back(x);
        return;
    }
    
    void pop() {
        
        if(!c.empty())c.pop_back();
        return;
    }
    
    int top() {
        
        return c.back();
    }
    
    int getMin() {
        auto p=min_element(c.begin(),c.end());
         return *p;
    }
private:
    vector<int> c;
};

改进一

class MinStack {
public:
    MinStack() {mins.push_back(INT_MAX);}
    
    void push(int x) {
        c.push_back(x);
        int _min=min(mins.back(),x);
        mins.push_back(_min);
        return;
    }
    
    void pop() {
        if(!c.empty()){
            c.pop_back();
            mins.pop_back();
        }
        return;
    }
    
    int top() {
        
        return c.back();
    }
    
    int getMin() {
         return mins.back();
    }
private:
    vector<int> c;
    vector<int> mins;
};