【被虐了】详解一次shopee面试算法题:最小栈的最优解

来源公众号:苦逼的码农

作者:帅地

前阵子面试的时候,在 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 栈中元素以及最小值的变化如下

【被虐了】详解一次shopee面试算法题:最小栈的最优解

上面表格是 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;
    }
 }

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

四、总结

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

原文始发于微信公众号(苦逼的码农):【被虐了】详解一次shopee面试算法题:最小栈的最优解

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 【被虐了】详解一次shopee面试算法题:最小栈的最优解

我还会在以下平台发布内容

GitHub 哔哩哔哩