题目描述

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

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

示例:

输入：

[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：

[null,null,null,null,-3,null,0,-2]

解释：

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

提示：

pop、top 和 getMin 操作总是在 非空栈 上调用。

题解思路

使用额外的栈（同步辅助栈）来完成。

由于栈有后进先出的特点。
假设元素a入栈时，栈里有元素 b、c、d，那么只要 a 在栈中，b、c、d 就一定会在栈中，因为在 a 被出栈前，b、c、d 不会被出栈。

我们使用同步辅助栈来依次存储新元素在入栈时当前整个栈的最小值。
当元素a入栈时，将当前整个栈的最小值min入栈到同步辅助栈中存储起来。

如果知道栈顶元素是a，那就可以直接知道此时原栈的最小值min了。

同步辅助栈与原栈的同步关系

入栈

1. 当原栈为空，新元素a入栈时，将新元素a拷贝一份，并入栈到辅助栈当中。
2. 当原栈非空，新元素k入栈时，取出辅助栈的栈顶元素min_top，与k比较，将min{k, min_top}入栈到辅助栈中去。

出栈

1. 原栈有元素出栈，辅助栈同时将栈顶元素弹出。

在任意一个时刻，原栈内元素的最小值就存储在辅助栈的栈顶中。

代码

#define MAXSIZE 1600

typedef struct {
    // 只用一个(数组模拟的)栈来同时模拟原栈、同步辅助栈并存
    // 原栈：偶数，0,2,4......
    // 辅助栈：奇数，1,3,5......
    int top;
    int *data;
} MinStack;

/** initialize your data structure here. */

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

void minStackPush(MinStack* obj, int x) {
    if(obj->top == MAXSIZE-1){
        // 栈满了，不做任何操作
    } else if(obj->top == -1){
        // 原栈
        obj->top++;
        obj->data[obj->top] = x;
        // 辅助栈
        obj->top++;
        obj->data[obj->top] = x;
    } else {
        // 当原栈非空，新元素k入栈时，取出辅助栈的栈顶元素min_top，与k比较，将`min{k, min_top}`入栈到辅助栈中去
        int tmp = obj->data[obj->top];
        // 原栈
        obj->top++;
        obj->data[obj->top] = x;
        // 辅助栈
        if(tmp < x){
            obj->top++;
            obj->data[obj->top] = tmp;
        } else {
            obj->top++;
            obj->data[obj->top] = x;
       }
    }
}

void minStackPop(MinStack* obj) {
    if(obj->top != -1){
        // 原栈
        obj->top--;
        // 辅助栈 
        obj->top--;
    }
}

int minStackTop(MinStack* obj) {
    if(obj->top == -1){
        return; // 返回空（void）
    }    
    return obj->data[obj->top-1]; // 必须减1，减1才是原栈的栈顶
}

int minStackGetMin(MinStack* obj) {
    // 在任意一个时刻，原栈内元素的最小值就存储在辅助栈的栈顶中
    return obj->data[obj->top];
}

void minStackFree(MinStack* obj) {
    free(obj->data);
    obj->data = NULL;
    free(obj);
    obj = NULL;
}

提交

优秀、精明的题解

1. 【精选】使用辅助栈（同步和不同步)
2. 详细通俗的思路分析，多解法