# LeetCode – Min Stack
Date: 2019-07-10


# 题目：

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.

**Example:**

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

# 解题：

    与普通栈不同，增加了一个返回栈最小值的功能， 这里使用了两个栈， 一个保存数据 ， 一个保存压栈过程中出现过的最小值。

         数据入栈，如果值大于等于当前最小值就入栈，注意这里的等于条件， 出最小值栈会判断是否与当前数据栈值一致，如果不增加等于条件， 会导致最小栈先于数据栈清空， 后续无法获取最小值。

          数据出栈时 ，在最小值栈中判断一下是否是当前最小值， 如果是，将最小值栈出栈。 

# 实现：

```

typedef struct {
    int *arr;
    int cnt;
    int *min;
    int mincnt;
    int limit;
    
} MinStack;

/** initialize your data structure here. */

MinStack* minStackCreate() {
    MinStack* obj = (MinStack*)malloc(sizeof(MinStack));
    obj->limit = 8192;
    obj->arr = (int*) malloc(sizeof(int)*(obj->limit));
    obj->min = (int*) malloc(sizeof(int)*(obj->limit));
    obj->cnt =0;
    obj->mincnt =0;
    return obj;
}

void minStackPush(MinStack* obj, int x) {
    obj->arr[obj->cnt++] = x;
    if (obj->mincnt==0 || x <= obj->min[obj->mincnt-1]){
        obj->min[obj->mincnt++] = x;
    }
  
}

void minStackPop(MinStack* obj) {
    
    if ( obj->arr[obj->cnt-1] == obj->min[obj->mincnt-1] ){
        obj->mincnt--;
    }
    obj->cnt--;
  
}

int minStackTop(MinStack* obj) {
   return obj->arr[obj->cnt-1];
}

int minStackGetMin(MinStack* obj) {
  return obj->min[obj->mincnt-1];
}

void minStackFree(MinStack* obj) {
    free(obj->arr);
    free(obj->min);
    free(obj);
    return;
}

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, x);
 
 * minStackPop(obj);
 
 * int param_3 = minStackTop(obj);
 
 * int param_4 = minStackGetMin(obj);
 
 * minStackFree(obj);
*/
```