Leetcode——155. 最小棧

思路：設定一個坐标loc_min指向最小的元素，然後每次入棧的時候比較入棧的元素是否為最小值。需要注意的一點是，出棧的時候需要考慮出棧的元素恰好為最小棧的情況。

ps：本題用數組來當作棧，空間複雜度可能不如寫好的stack好，因為數組不能動态擴容是以要盡量開的大一點。但是思路近似。

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

    int stack_int[100000];
    int loc;
    int min;
    int min_loc;

    MinStack()
    {
        loc=0;
        min=0;
        min_loc=0;
    }
    
    void push(int x) 
    {
        stack_int[loc]=x;
        loc++;
        if(loc==1)
        {
            min=x;
            min_loc=0;
        }
        else
        {
            if(x<min)
            {
                min=x;
                min_loc=loc-1;
            }
        }
    }
    
    void pop() 
    {
        loc--;
        if(min_loc==loc&&loc>0)
        {
            min=stack_int[0];
            min_loc=0;
            for(int i=0;i<loc;i++)
            {
                if(stack_int[i]<min)
                {
                    min=stack_int[i];
                    min_loc=i;
                }
            }
        }
    }
    
    int top() 
    {
        int loc_top=loc-1;
        return stack_int[loc_top];
    }
    
    int getMin() 
    {
        return stack_int[min_loc];
    }
};

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