题目：

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:

1
2
3
4
5
6
7
8

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.

解题：

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

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

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

实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


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