手撕最小栈：两个栈实现 O(1) 获取最小值

最小栈要求：

push
pop
top
getMin

都尽可能做到 O(1)。

核心思路：

一个栈存正常数据，一个栈同步保存“当前最小值”。

1. 数据结构

#define MAX_SIZE 10000

typedef struct {
    int *x_stack;       // 正常栈
    int *min_stack;     // 最小值栈
    int x_top;
    int min_top;
} MinStack;

两个栈保持同步。

例如依次：

push 5
push 3
push 7
push 2

得到：

x_stack：
5 3 7 2

min_stack：
5 3 3 2

min_stack 的每一层保存的是：

当前这一层的最小值。

---

2. Push

void minStackPush(MinStack *obj, int x)
{
    obj->x_stack[++obj->x_top] = x;

    if (obj->min_top == -1 ||
        x < obj->min_stack[obj->min_top])
    {
        obj->min_stack[++obj->min_top] = x;
    }
    else
    {
        obj->min_stack[++obj->min_top] =
            obj->min_stack[obj->min_top];
    }
}

所以：

新元素更小
    ↓
min_stack 压入新元素

否则
    ↓
min_stack 继续保存之前的最小值

---

3. Pop

两个栈同步弹出：

void minStackPop(MinStack *obj)
{
    if (obj->x_top == -1)
        return;

    obj->x_top--;
    obj->min_top--;
}

例如：

之前：

x_stack：   5 3 7 2
min_stack： 5 3 3 2

pop()

之后：

x_stack：   5 3 7
min_stack： 5 3 3

当前最小值自然恢复成 3。

---

4. Top 和 GetMin

int minStackTop(MinStack *obj)
{
    return obj->x_stack[obj->x_top];
}

int minStackGetMin(MinStack *obj)
{
    return obj->min_stack[obj->min_top];
}

getMin() 不需要遍历整个栈：

min_stack 栈顶
     ↓
当前最小值

因此是 O(1)。

---

5. 整体思路

x_stack
    ↓
保存真实数据

min_stack
    ↓
保存每一层的最小值

例如：

x_stack：    5  3  7  2
min_stack：  5  3  3  2
             ↑  ↑  ↑  ↑
           当前每层最小值

一句话记忆：

正常栈存数据，辅助栈存历史最小值；两个栈同步 Push、Pop，最小值直接看辅助栈栈顶。

这样就把 getMin() 从遍历 O(n) 降到了 O(1)。

#define MAX 10000

typedef struct
{
    int stack1_top;
    int *stack1;

    int stack2_top;
    int *stack2;
} MinStack;

MinStack* minStackCreate()
{
    MinStack *obj = malloc(sizeof(MinStack));

    obj->stack1 = malloc(sizeof(int) * MAX);
    obj->stack2 = malloc(sizeof(int) * MAX);

    obj->stack1_top = 0;
    obj->stack2_top = 0;

    return obj;
}

void minStackPush(MinStack* obj, int x)
{
    obj->stack1[obj->stack1_top++] = x;

    if (obj->stack2_top == 0 ||
        x < obj->stack2[obj->stack2_top - 1])
    {
        obj->stack2[obj->stack2_top++] = x;
    }
    else
    {
        obj->stack2[obj->stack2_top++] =
            obj->stack2[obj->stack2_top - 1];
    }
}

void minStackPop(MinStack* obj)
{
    if (obj->stack1_top == 0)
        return;

    obj->stack1_top--;
    obj->stack2_top--;
}

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

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

void minStackFree(MinStack* obj)
{
    free(obj->stack1);
    free(obj->stack2);
    free(obj);
}