康瑞部落

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.

• pop() -- Removes the element on top of the stack.

• top() -- Get the top element.

• getMin() -- Retrieve the minimum element in the stack.

解题思路：

主要是获得当前最小值的问题。我们可以用一个动态数组min存储当前最小值。若新压入的元素大于动态数组min最后一个元素，不做任何操作。否则（小于或等于）就压入min中。出栈的时候，若出栈元素等于min最后一个元素，则min数组出栈。这样便实现了常量时间找到栈中的最小值了。下面是代码：

class MinStack {
public:
    MinStack(){
        capcity=2;
        data = new int[capcity];
        size=0;
        
        minCapcity=2;
        min = new int[minCapcity];
        minSize = 0;
    }
    ~MinStack(){
        delete[] data;
        delete[] min;
    }
    void push(int x) {
        if(size>=capcity){
            int* p=data;
            capcity = 2*capcity;
            data=new int[capcity];
            std::memcpy(data, p, sizeof(int)*size);
            delete[] p;
        }
        data[size++]=x;
        
        if(minSize==0){
            min[minSize++]=x;
        }else if(min[minSize-1]>=x){
            if(minSize>=minCapcity){
                int* p=min;
                minCapcity = 2*minCapcity;
                min = new int[minCapcity];
                std::memcpy(min, p, sizeof(int)*minSize);
                delete[] p;
            }
            min[minSize++]=x;
        }
    }

    void pop() {
        if(size>0){
            size--;
            if(data[size]==min[minSize-1]){
                minSize--;
            }
        }else{
            throw exception();
        }
    }

    int top() {
        if(size>0){
            return data[size-1];
        }else{
            throw exception();
        }
    }

    int getMin() {
        return min[minSize-1];
    }
private:
    int size;
    int capcity;
    int* min;
    int minSize;
    int minCapcity;
    int* data;
};

二次刷题（2015-08-05）

同样的思路。注意min栈存储的是一个递减序列，栈顶是当前栈中最小的值。这样，每个操作其实都能够在常量时间完成。

class MinStack {
public:
    void push(int x) {
        ss.push(x);
        if(min.empty() || x<=min.top()){
            min.push(x);
        }
    }

    void pop() {
        int x = ss.top();
        ss.pop();
        if(x==min.top()){
            min.pop();
        }
    }

    int top() {
        return ss.top();
    }

    int getMin() {
        return min.top();
    }
private:
    stack<int> min;
    stack<int> ss;
};