【作业10】shopee真题：最小栈变形题

对应课程链接：拿捏算法面试课程

这是我在面试遇到的问题，大家可以想一想，如何实现时间和空间都是 O(1)，核心突破口在于数值范围，有一定难度。
问题描述：
实现一个这样的栈，这个栈除了可以进行普通的push、pop操作以外，还可以进行getMin的操作，getMin方法被调用后，会返回当前栈的最小值。栈里面存放的都是 int 整数，并且数值的范围是 [-100000, 100000]。要求所有操作的时间复杂度是 O(1)。

附加：如果空间复杂度也能O(1)的话可加分

打卡要求：时间+空间都是O（1）就当作选做吧，你可以说一说你的想法，让空间/尽可能小勒。

参考答案

答案已经出来了，大家看这个文章解析：Shopee面试：最小栈的最优解

shuaidi

更新于 3 年前 151 3

共以下 3 个回答

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

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

0 赞同 0 条回复

秊永久会员 2023年5月25日下午5: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;
    }
}

0 赞同 0 条回复

Everglow 永久会员 2023年5月8日下午4:28

时间O(1) 空间O(1)
“java
class MinStack {

Stack<Integer> stack;
int min;

/** initialize your data structure here. */
public MinStack() {
    this.stack = new Stack<>();
    //保存当前栈内的最小值
    min = Integer.MAX_VALUE;
}

public void push(int x) {
    //如果需要更新最小值，则先保留（压入）当前最小值，再压入x
    if(x <= min) {
        stack.push(min);
        min = x;
    }
    stack.push(x);
}

public void pop() {
    //如果弹出的是最小值，则需要pop两次 更新最小值
    if(stack.peek().equals(min)) {
        stack.pop();
        min = stack.pop();
    } else {
        stack.pop();
    }
}

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

public int getMin() {
    return min;
}

}
“

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【作业10】shopee真题：最小栈变形题

参考答案

共以下 3 个回答

辅助栈

辅助栈 pro

进阶：辅助常量

# 回答此问题 取消回复

# 回答此问题取消回复