【今日算法】4月21日-最小栈的最优解

前阵子面试的时候，在 shopee 的一面中，问了我一道最小栈的问题，关于最小栈的问题，我以前是做过的，以为是送分题，最结果最优解没写出来，不过也脑补了一些优化，算是答的还行。下面我先大致描述下这道题，然后一步步给出最优解以及我在面试中是解法（面试中给出了几个优化，但想不出最优解）。题目如下：

实现一个这样的栈，这个栈除了可以进行普通的push、pop操作以外，还可以进行getMin的操作，getMin方法被调用后，会返回当前栈的最小值。栈里面存放的都是 int 整数，并且数值的范围是 [-100000, 100000]。要求所有操作的时间复杂度是 O(1)。 附加：如果空间复杂度也能O(1)的话可加分。

解答

对于这道题，如果是要求时间复杂度为 O(1)，空间复杂度为 O(n) 或者 时间复杂度为 O(n)，空间复杂度为 O(1) 的话，还是相对比较简单一点的，不过我猜想仍然有部分同学不会，所以我下面都稍微讲解一下。不过如果要求时间复杂度和空间复杂度都是 O(1) 的话，就比较难了，反正我当时是没做出来，只给出了一些优化的思路。

时间复杂度 O(n) + 空间复杂度 O(1) 这个我不讲，因为这个很简单，就是获取最小栈的时候，每次都遍历一次栈，把最小栈返回去就可以了，估计也没有人会问你这个方法

一、时间 O(1) + 空间 O(n)

这个要求其实也不难，我们可以用一个辅助栈来存放最小值。例如我们有两个栈 stack 和 helper，stack 是目标栈，helper 是辅助栈，用来存放最小值。每次 getMin 的时候，直接从 helper 栈顶获取即可。下面重点讲一下 push 操作。

每次进行 push 操作的时候，进行如下操作（假设要 push 的元素是 t）

1、对于 stack 栈，我们按照正常情况把元素 push 到栈顶就可以了。

2、然后要把元素 t push 到 helper 栈顶的时候，要先把 t 与 helper 栈顶的元素（假设是 a）进行比较，如果 t <= a，则把元素 t push 到 helper 的栈顶，如果 t > a，这个时候，我们不把 t push 进去，而是重复把 a push 到 helper 的栈顶。

我举个例子吧，例如我们要把数组 arr = {2, 1, 3} 都放入栈中，则存放过程如下：

1、首先 push 2。由于刚开始 stack 和 helper 都是空的，所以直接把 2 放入，此时目标栈和辅助栈的值如下：stack = {2}，helper = {2}。

2、接下来 push 1。由于 helper 栈顶元素比 1 大，所以直接把 1 放入 helper 的栈顶，此时：stack = {2, 1}，helper = {2, 1}。

3、接下来 push 3，由于 helper 栈顶元素比 3 小，所以重复把 栈顶的元素再次入栈，此时：stack = {2, 1, 3}，helper = {2, 1, 1}。

对于 pop 操作，直接把两个栈的栈顶元素删除即可，所以具体代码如下：

public class 设计一个有gitMin的栈 {
    // 定义两个栈
    public static Stack<Integer> stack = new Stack<>();
    public static Stack<Integer> helper = new Stack<>();

    public static void push(Integer data) {
        // 目标栈正常入栈
        stack.push(data);

        if (helper.isEmpty()) {
            helper.push(data);
        }
        // 判断栈顶与要 push 元素的大小
        else if (helper.peek() <= data) {
            helper.push(data);
        } else {
            helper.push(helper.peek());
        }
    }

    public static Integer pop() {
        if (stack.isEmpty()) {
            return null;
        }
        helper.pop();
        return stack.pop();
    }
    public static Integer getMin() {
        return helper.isEmpty() ? null : helper.peek();
    }
}

二、被怼

不过接着面试官问我，你这个空间复杂度是 O(n)，可以优化到空间复杂度为 O(1) 吗？

这时有点小紧张，因为我之前看的书和别人的讲解中，根本没看过时间和空间都是 O(1) 的解法，不过这道题中，有一个条件限制，就是数值的范围是 [-100000, 100000]，我知道，这个数值限制，一定是一个突破口，可是硬是没想出来要怎么利用，于是我就按照自己的理解，给出了如下的优化方案：

1、优化1

刚才我们在对 helper 进行 push 操作的时候，如果栈顶的元素较小，那么我们是重复把栈顶的元素重复 push 进去的，显然，这是一个单调栈，并且栈顶的元素只会越来越小，假如栈顶的元素很小的话，那么有可能会出现，helper 的栈中有很多一样的元素，例如 helper = {2, 1, 1, 1, 1, 1, 1, 0, 0, 0 , 0, 0, 0}。

为了解决这个问题，我们可以用一个数值，来表示此处有多少个连续的元素，例如上面的辅助栈中有 1 个 2，6 个 1，6 个 0，那么我们可以这样来表示：helper = {2, 1, 1, 6, 0, 6}。这样的话，辅助栈用到的空间可以小一点。

当然，也有可能用的更多了，例如栈中基本没有连续的元素，例如原本 helper = {3， 2， 1}，则会变成 helper = {3, 1, 2, 1, 1, 1}。当然，这是极端的情况。

2、优化2

面试官问我还能有其他方法吗？

显然，我上面的优化中，并没有用到数值范围 [-100000, 100000] 这个条件，所以肯定是不行的，该怎么用利用到这个条件呢？

这个时候我是想到了位运算，一个 int 是 32 位，我打算把它分割成两部分，前面 16 位来存放目标值，后面 16 位来存放最小栈。也就是说，我不需要辅助栈 helper 了，只需要一个 stack 就够了，然后用元素的后 16 位来充当 helper 辅助栈的功能。

例如对于最上面的例子 stack = {2, 1, 3}, helper = {2, 1, 1}。那么这里只需要用一个 stack 来存放就可以了。把元素分割成 两部分，前面 16 位存放 stack 里面的值，后面 16 位存放 helper 里面的值，即 stack = {(2,2), {1, 1}, (3, 1)}。然后每次取值的时候，在通过移位的方法来获取值。

想到了这个方法，虽然没有想出最优解，不过我看面试官还是有那么点小满意的，不过我这个方法的数值范围限制是 [-2^15, 2^15 – 1]，而题目的限制是 [-100000, 100000]，所以会溢出，所以行不通，不过至少提供了一种思路。当然我可以用 long 类型的来存放，不过 Long 所需要的空间是 int 的两倍，所以我觉得也不大行，还是没有达到 O(1)。

然后我自己也想不出啥方法了，后面去网上和群里问被人才找到解法。下面我稍微说下这个方法

三、最优解

这种方法的话，我们的 stack 栈中，不能存放原始数值，而是应该存放 差值，啥差值？就是存放栈顶与最小值的差值。我还是详细一点给大家讲一个案例吧，案例配合代码，应该还是挺好理解的，例如 arr = {2, 1, 3, 0}，那么把这些元素入栈时，stack 栈中元素以及最小值的变化如下

上面表格是 push 时，栈中数值的变化，然后再进行 getMin 和 pop 可以通过相应的判断获取，直接看我的代码实现吧，我会进行相应解释，挺好懂，代码如下：

public class 设计一个有gitMin的栈 {

    private Stack<Integer> stack = new Stack<Integer>();
    private int min;

    public void push(int x) {
        if (stack.isEmpty()) {
            min = x;
            stack.push(0);
        } else {
            // 计算差值
            int compare = x - min;
            stack.push(compare);
            // 如果差值小于0，显然 x 成为最小值，否则最小值不变
            min = compare < 0 ? x : min;
        }
    }

    public void pop() {
        int top = stack.peek();
        // 如果top小于0，显然最小值也一并会被删除，此时更新最小值
        min = top < 0 ? (min - top) : min;
        stack.pop();
    }

    public int getMin() {
        return min;
    }
 }

如果没有进行数值范围限制，上面的方法能行吗？答是不行，因为数值没有限制的话，差值的计算可能会溢出。

四、总结

虽然这道题总体不难，不过一道题的解法多种多样，我们千万不能止步于最简单的解法，而应该寻找最优解。后面我也会讲一些面试相关的题，并且每次讲的时候，都会给出详细的解答，从暴力一步步到最优。

来源 | 苦逼的码农

作者 | 帅地