本文共 3277 字，大约阅读时间需要 10 分钟。

题目描述

设计一个支持 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，那就可以直接知道此时原栈的最小值min了。

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

入栈

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

出栈

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

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

代码

#define MAXSIZE 1600typedef 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;}

提交

优秀、精明的题解

补充

Java版，优化题解：

class MinStack {
       /** initialize your data structure here. */    private Stack
   
     stack;        public MinStack() {
           // 用数组模拟栈        // 只用一个栈来同时实现原栈、同步辅助栈并存        // 栈中每个元素：[当前值, 当前最小值]        stack = new Stack
    
     ();    }        public void push(int val) {
           if (stack.isEmpty())            stack.push(new int[] {
   val, val});        else            stack.push(new int[] {
   val, Math.min(val, stack.peek()[1])});    }        public void pop() {
           stack.pop();    }        public int top() {
           return stack.peek()[0];    }        public int getMin() {
           return stack.peek()[1];    }}/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
    
   

转载地址：http://dlatf.baihongyu.com/