Shopee面试：最小栈的最优解

经典算法题讲解 5月前 0 512

前阵子面试的时候，在 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;
    }
 }

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

四、总结

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

算法

发表回复取消回复

后才能评论

e=mc² 普通 2024年3月10日下午10:29

差值栈并且这种栈的peek方法应该是无法实现的

登录以回复
紫芝普通 2024年3月7日上午8:49
谢谢，获得了新方法，时空复杂度均为O(1)。

“`c++
class MinStack {
private:
stack st;
int min;
public:
/** initialize your data structure here. */
MinStack() {
```
}

void push(int x) {
    if (st.empty()) {
        min = x;
        st.push(0);
    } else {
        st.push(x-min);
        min = x-min > 0 ? min : x;
    }
}

void pop() {
    int top = st.top();
    st.pop();
    min = top < 0 ? min - top : min;
}

int top() {
    int top = st.top();
    return top < 0 ? min : min + top;
}

int getMin() {
    return min;
}
```
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/

“`
登录以回复

云无深雁影普通 2024年3月6日下午7:52

class MinStack {
//时空均为O1的解法
Stack s ;
int min;

/** initialize your data structure here. */
public MinStack() {
    s = new Stack<Integer>();
}

public void push(int x) {
    if(s.empty()){
        s.push(0);
        min = x;
    }
    else{
        int y = x - min;
        s.push(y);
        if(y < 0)
            min = x;
    }
}

public void pop() {
    int y = s.pop();
    if(y < 0)
        min = min - y;
}

public int top() {
    return s.peek() + min;
}

public int getMin() {
    return min;
}

}

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/

Thaddeus 永久会员 2024年3月6日上午11:19

差值栈

class Solution {
public:
    void push(int x) {
        if(stk.empty()) { // 栈为空
            _min = x;  // 第一个元素就是最小元素
            stk.push(0); // 其与自身差值为0
        } else { // 栈不为空
            int compare = x - _min; // 计算当前元素与栈中最小元素的差值
            stk.push(compare); // 将差值入栈
            _min = compare < 0 ? x : _min; // 更新栈中最小元素
        }
    }
    
    void pop() {
        int _top = stk.top(); // 取出栈顶那个差值
        _min = _top < 0 ? (_min - _top) : _min; 
        stk.pop();
    }
    
    /* 最小值在哪里：
        1.在push的时候，_min不断更新，永远保存最小值 
        2.在pop的时候，若栈顶那个差值>0，说明该差值对应的元素>_min，则不更新_min；
                       若栈顶那个差值<0，说明该差值对应的元素就是_min，则要更新_min，
        3.如何更新_min:在插入栈顶这个差值(_top)对应的元素之前，最小值为_premin,插入之后最小值为_min，
                        _top = _min - _premin,则_premin = _min - _top
    */
    int getMin() {
        return _min; 
    }


private:
    stack stk; // 存放栈顶与最小值的差值
    int _min; // 存放当前栈中最小的元素
    
};

heathhou 普通 2024年3月5日下午9:00

妙啊

登录以回复

mpweixin用户普通 2023年10月18日下午6:05

如下所示：
”’
#include
#include

using namespace std;

class Stack{
private:
stack stack;
int min;

public:
    void push(int x){
        if(stack.empty()){
            stack.push(0);
            min = x;
        }
        else{
            int compare = x - min;
            stack.push(compare);
            min = compare<0?x:min;
        }
    }

    void pop(){
        int top = stack.top();
        min = top<0?(min - top):min;
        stack.pop();
    }

    void top(){
        return stack.top() < 0 ? min : stack.top() + min;
    }


    int getMin(){
        return min;
    }

};
”’

泡芙永久会员 2023年9月15日下午5:43

class MinStack {
    Stack<Integer> stack; // 存放差值
    int min; //存储最小值

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int val) {
        if (stack.isEmpty()) {
            min = val;
            stack.push(0); 
        } else {
            // 计算差值
            int res = val - min; // 可能会发生溢出
            stack.push(res);
            // 如果差值小于0，更新val成为最小值，否则最小值不变
            min = res < 0 ? val : min;
            // 注意：一定是先压入，在更新，因为min一定是当前栈中的最小值
        }
    }

    public void pop() {
        int top = stack.peek();
        // 当top小于0时，说明弹出元素是当前栈中的最小值，此时要更新最小值
        min = top < 0 ? (min - top) : min;
        stack.pop();
    }

    public int top() {
        // 注意：若当前栈顶小于等于0，说明最小值就是栈顶元素，否则就是peek+min
        return stack.peek() < 0 ? min : stack.peek() + min;
    }

    public int getMin() {
        return min;
    }
}

招舟子普通 2023年8月25日上午10:29

有数据范围限制
可以使用差值栈

登录以回复
天亮说晚安普通 2023年8月20日上午10:09

差值栈，但要注意数值范围限制

登录以回复

今天没时间刷题普通 2023年7月26日下午11:30

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
    }

    stack<long> st;
    long _min;

    void push(long x) {
        if(st.empty())
        {
            st.push(0);
            _min = x;
            return;
        }

        long diff = x - _min;
        st.push(diff);
        if(diff < 0)//差值小于0才需要更新
        {
            _min = x;
        }
    }

    void pop() {
        long top = st.top();
        st.pop();
        if(top < 0)//差值小于0才需要更新
        {
            _min -= top; 
        }
    }

    long top() {
        return st.top() <= 0 ? _min : (_min + st.top());
    }

    long min() {
        return _min;
    }
};

周小二普通 2023年7月15日下午4:17

 class MinStack {
    private Stack<Long> diffStack;
    private long min;

    /** initialize your data structure here. */
    public MinStack() {
        diffStack = new Stack<>();
    }

    public void push(long x) {
        if (diffStack.isEmpty()) {
            diffStack.push(0L);
            min = x;
        } else {
            //栈中元素为x与min的差值
            diffStack.push(x - min);
            min = Math.min(x, min);
        }
    }

    public void pop() {
        if (diffStack.isEmpty()) {
            return;
        }
        //如果当前差额大于等于0，不更新最小值
        if (diffStack.peek() >= 0) {
            long diff = diffStack.pop();
            return;
        }
        //如果当前差额小于0，弹出栈顶元素，更新最小值
        min = min - diffStack.pop() ;
        return;
    }

    public long top() {
        if (diffStack.peek() <= 0) {
            return min;
        }
        return diffStack.peek() + min;
    }

    public long min() {
        return min;
    }
}

Marshan 普通 2023年7月14日下午3:06

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

#include<iostream>
#include<stack>

using namespace std;

class Stack{
    private:
        stack<int> stack;
        int min;

    public:
        void push(int x){
            if(stack.empty()){
                stack.push(0);
                min = x;
            }
            else{
                int compare = x - min;
                stack.push(compare);
                min = compare<0?x:min;
            }
        }

        void pop(){
            int top = stack.top();
            min = top<0?(min - top):min;
            stack.pop();
        }

        int getMin(){
            return min;
        }
};
int main(){

}

北辰普通 2023年7月13日下午12:10

public class 设计一个有getMin的栈 {
    public Stack<Integer> stack = new Stack<>();
    public int min;//存储最小值

    public void push(int x) {
        if(stack.isEmpty()) {
            stack.push(0);
            min = x;
        }else {
            stack.push(x-min);
            min = x-min<0?x:min;
        }
    }

    public void pop() {
        int top = stack.pop();
        min = top<0?min-top:min;
    }

    public int getMin() {
        return min;
    }

    public static void main(String[] args) {

    }
}

阿尚普通 2023年7月11日下午8:25

//来看我的
//一个栈实现
class MinStack {
    Stack<Integer> stack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int x) {
        if(stack.isEmpty() || x < stack.peek()){
            stack.push(x);
            stack.push(x);
        }else{
            int minVal = stack.peek();
            stack.push(x);
            stack.push(minVal);
        }
    }

    public void pop() {
        if(stack.isEmpty()) return;
        stack.pop();
        stack.pop();
    }

    public int top() {
        int minVal = stack.pop();
        int topVal = stack.peek();
        stack.push(minVal);
        return topVal;
    }

    public int min() {
        return stack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

3_🔥 永久会员 2023年7月4日下午3:51

import java.util.Stack;

public class minStack {
    private Stack<Integer> stack = new Stack<>();
    private int min;
    //push()
    void push(int x){
        if (stack.isEmpty()) {
            min = x;
            stack.push(0);
        }else {
            int compare = x - min;
            stack.push(compare);
            min = compare < 0 ? x : min;
        }
    }
    void pop(){
        int top = stack.peek();
        min = top < 0 ? (min - top) : min;
        stack.pop();
    }
    int getMin(){
        return min;
    }
}

差值，最优解，注意数据范围

mpweixin用户普通 2023年6月24日下午9:18

记录入栈元素和最小值的差
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_element = float('inf')

    def push(self, x: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.min_element = x
        else:
            self.stack.append(x - self.min_element)
            self.min_element = min(self.min_element, x)

    def pop(self) -> None:
        tmp = self.stack.pop()
        self.min_element = self.min_element if tmp >= 0 else self.min_element - tmp

    def top(self) -> int:
        return self.min_element if self.stack[-1] < 0 else self.min_element + self.stack[-1]

    def min(self) -> int:
        return self.min_element


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

秊永久会员 2023年5月24日下午10:47

辅助栈

class MinStack {
    // 两个栈：主栈和辅助栈
    Stack<Integer> st1;
    Stack<Integer> st2;

    public MinStack() {
        st1 = new Stack<>();
        st2 = new Stack<>();
    }

    public void push(int val) {
        if (st1.empty()) {
            st1.push(val);
            st2.push(val);
        } else {
            st1.push(val);
            int min = st2.peek();
            min = min < val ? min : val;
            st2.push(min);  // 辅助栈只记录当前的最小值
        }
    }

    public void pop() {
        st1.pop();
        st2.pop();
    }

    public int top() {
        return st1.peek();
    }

    public int getMin() {
        return st2.peek();
    }
}

辅助栈 pro

class MinStack {
    Stack<Node> st;

    // 用一个 Node 同时存储 val 和当前的 min 值
    class Node {
        int val;
        int min;

        Node(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }

    public MinStack() {
        st = new Stack<Node>();
    }

    public void push(int val) {
        if (st.empty()) {
            Node tmp = new Node(val, val);
            st.push(tmp);
        } else {
            Node pre = st.peek();
            int min = pre.min < val ? pre.min : val;
            Node tmp = new Node(val, min);
            st.push(tmp);
        }
    }

    public void pop() {
        st.pop();
    }

    public int top() {
        return st.peek().val;
    }

    public int getMin() {
        return st.peek().min;
    }
}

进阶：辅助常量

class MinStack {
    Stack<Integer> st;
    int min;

    public MinStack() {
        st = new Stack<>();
    }

    public void push(int val) {
        if (st.empty()) {
            min = val;
            st.push(0);
        } else {
            int diff = val - min;  // 可能会发生溢出
            if (diff < 0) {   // 差值小于零，意味着当前 val 为最小，需要更新 min 值
                min = val;
            } 
            st.push(diff);
        }
    }

    public void pop() {
        int tmp = st.pop();
        if (tmp < 0) {   // 如果弹出了最小值，就要记得更新 min 值
            min = min - tmp;
        }
    }

    public int top() {
        return st.peek() < 0 ? min : st.peek() + min;
    }

    public int getMin() {
        return min;
    }
}

鸿渐普通 2022年10月29日上午10:13

 //只用一个栈来解决
    private Deque<Integer> stack;

    private Integer min;

    public MinStack() {
        stack = new ArrayDeque<>();
        min = Integer.MAX_VALUE;
    }

    public void push(int x) {
        if (x <= min) {
            min = x;
        }
        //先放入最小值再 放入值
        stack.push(min);
        stack.push(x);
    }

    public void pop() {
        //第一次pop 弹出实际存入的数
        stack.pop();
        //第二次弹出弹出的是对应的最小值
        stack.pop();
        if (!stack.isEmpty()) {
            //修改此时的最小值
            int temp = stack.pop();
            min = stack.pop();
            //再将 最小值和存入的值放回栈当中
            stack.push(min);
            stack.push(temp);
        }else {
            //如果此时的栈已经空了 清空最小值恢复到原来的
            min=Integer.MAX_VALUE;
        }
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return min;
    }

解答