包含min函数的栈｜刷题打卡-一一网

掘金团队号上线，助你 Offer 临门！点击查看详情

一、题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.
复制代码

限制

各函数的调用总次数不超过 20000 次
复制代码

二、思路分析

我的思路

说实在的没想出来！想要实现O(1) 除了数学算法，也想过有什么合适的hash算法。
其实也想到了使用辅助栈。但是没有自己思考因为数据结构是栈的特性。

最佳思路

需要借助辅助栈
- 需要一个辅助栈B，专门存放当前主栈A中最小的元素，即如果push的时候，只有发现了push的元素是小于B栈顶元素才push进去B
- 这样求min的时候我直接返回B栈顶元素就行了。
- 当pop的时候，最关键了，如果AB此时元素都在栈顶。那么这2个需要同时抛出。
我为什么没有想到？
- 对min的思考比较混乱，min其实就是取最小！但是他不会弹出。如果第一个放1，后面放3,5,3,2 这些乱序的都无所谓，只要没有pop到1，那么这个栈的最小元素始终都是1
- 我也不知道当时是怎么想的，硬是在想这个辅助栈B应该和A元素相同，只不过排序的（这根本无法做到O(1)）主要min只是需要知道最小元素，
- 你在push的过程中，你可以获取到最小的元素！只要这个元素没有被pop，那么它始终都是这个栈的最小元素。

三、AC 代码

我的写法：

/**
 * 这里可以直接使用栈去做的，没必要像我这么麻烦。
 */
ArrayList<Integer> stackA;
// B 存放A的最小元素
ArrayList<Integer> stackB;
// A的index -- 因为栈结构不是基础结果，以为我需要自己模拟栈，其实可以直接使用java的栈，题目是接受java自带栈的
int index;
// B的index -- 为了模拟栈，其实可以直接使用java的栈
int indexB;
/**
 * initialize your data structure here.
 */
public MinStack() {
    stackA = new ArrayList<>();
    stackB = new ArrayList<>();
    index = -1;
    indexB = -1;
}
public void push(int x) {
    stackA.add(x);
    index++;
    if (stackB.size() == 0 || stackB.get(indexB) >= stackB.add(x);
        indexB++;
    }
}
public void pop() {
    if (stackA.size() == 0) {
        return;
    }
    if (stackB.get(indexB).equals(stackA.get(index)
        // 这个remove int的移除的是索引，Integer移除的是这个元素里面的该i
        stackB.remove(indexB);
        indexB--;
    }
    stackA.remove(index);
    index--;
}
public int top() {
    return stackA.get(Math.max(0, index));
}
public int min() {
    return stackB.get(Math.max(0, indexB));
}
复制代码