题目要求

要求完成最小栈数据结构，可以像栈一样后进先出，并且可以以$O(1)$的时间得到栈中的最小元素

方法一：辅助栈，空间复杂度$O(n)$

辅助栈和主栈，一直保持同样的高度，如果从栈底到栈顶主栈是-2，-1，-3，5，那么辅助栈就是-2，-2，-3，-3 。

typedef struct {
    int stack[30000];
    int stack_min[30000];
    int top;
} MinStack;


MinStack* minStackCreate() {
    MinStack* obj = (MinStack *)malloc(sizeof(MinStack));
    obj->top = -1;
    return obj;
}

void minStackPush(MinStack* obj, int val) {
    int val_min = val;
    if(obj->top != -1)val_min = obj->stack_min[obj->top] < val ? obj->stack_min[obj->top] : val;
    obj->stack[++obj->top] = val;
    obj->stack_min[obj->top] = val_min;
}

void minStackPop(MinStack* obj) {
    obj->top--;
}

int minStackTop(MinStack* obj) {
    return obj->stack[obj->top];
}

int minStackGetMin(MinStack* obj) {
    return obj->stack_min[obj->top];
}

方法二：记录差值，空间复杂度$O(1)$

使用栈保存差值，使用min_val记录最小值，插入时，如果栈中没有元素，向栈中加入0，且min_val = val，有元素，则加入diff = val – min_val，若diff < 0，更新min_val。pop操作，若栈顶元素小于0，则pop出去了最小值，需要更新min_val。top操作，如果栈顶小于0，说明栈顶是最小值，直接返回min_val，否则返回min_val + 栈顶。

typedef struct {
    long long stack[30000];
    long long min_val;
    long long top;
} MinStack;


MinStack* minStackCreate() {
    MinStack* obj = (MinStack *)malloc(sizeof(MinStack));
    obj->top = -1;
    return obj;
}

void minStackPush(MinStack* obj, int val) {
    if(obj->top == -1){
        obj->stack[++obj->top] = 0;
        obj->min_val = val;
    } else {
        long long diff = val - obj->min_val;
        obj->stack[++obj->top] = diff;
        if(diff < 0)obj->min_val = val;
    }
}

void minStackPop(MinStack* obj) {
    if(obj->stack[obj->top] < 0){
        obj->min_val -= obj->stack[obj->top];
    }
    obj->top--;
}

int minStackTop(MinStack* obj) {
    if(obj->stack[obj->top] < 0)return obj->min_val;
    return obj->min_val + obj->stack[obj->top];
}

int minStackGetMin(MinStack* obj) {
    return obj->min_val;
}