Loading...
墨滴

MelodyJerry

2021/06/08  阅读:43  主题:雁栖湖

[LeetCode-155] 最小栈(酷酷的解法:一栈实现原栈+同步辅助栈并存)

1题目描述

设计一个支持 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 操作总是在 非空栈 上调用。

2题解代码

  • 一栈实现 原栈+同步辅助栈 并存
class MinStack {

    /** initialize your data structure here. */
    private Stack<int[]> stack;
    
    public MinStack() {
        // 用数组模拟栈
        // 只用一个栈来同时实现原栈、同步辅助栈并存
        // 栈中每个元素:[当前值, 当前最小值]
        stack = new Stack<int[]>();
    }
    
    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();
 */

3补充

大一时的C版本题解

现在看大一的题解,觉得还是有点行的,只用一个栈空间实现两个栈的操作。 怎么说呢,把这个题解放在文章里,就当是回忆吧~

使用额外的栈(同步辅助栈)来完成。

由于栈有后进先出的特点。

假设元素 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. 原栈有元素出栈,辅助栈同时将栈顶元素弹出。

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

4代码

#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;
}

5提交

MelodyJerry

2021/06/08  阅读:43  主题:雁栖湖

作者介绍

MelodyJerry