155.最小栈.md

题目描述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。

eg:

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

思路描述：设计类问题，不是很常见，我是用vector去实现的。

class MinStack {
private:
    vector<int> nums;
    int minIndex;
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {
        if(nums.size() == 0) minIndex = 0;
        else if(nums[minIndex] > x) minIndex = nums.size();
        nums.push_back(x);
    }
    
    void pop() {
        int minNum = nums[0];
        if(minIndex == nums.size() - 1){
            minIndex = 0;
            for(int i = 1; i < nums.size() - 1; i ++){
                if(nums[i] < minNum){
                    minNum = nums[i];
                    minIndex = i;
                }
            }
        }
        nums.pop_back();
    }
    
    int top() {
        return nums.back();
    }
    
    int getMin() {
        return nums[minIndex];
    }
};

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