【基本数据结构】变形题：最小栈的最优解

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

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

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

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

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

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

shuaidi

更新于 2 年前 205 16

共以下 16 个回答

LovLe 普通 2024年12月18日上午7:59

时间空间复杂度均为 O(1)。

stack保存当前最小值与x的差值。

什么时候更新最小值？
- 当diff差值<0，说明当前值更小，更新
- 当stack为空，初始入栈，更新最小值为x。那么初始stack元素应该是x-minx=diff，minx=x，diff=0。stack入栈为0
怎么pop，pop怎么退回最小值？
- 如果pop的diff<0，那么说明最小值被推出，要更新最小值为上一个最小值。根据diff=stack[-1]，diff=x-minx(上一个最小值)。所以minx=x-diff退回了上一个最小值。因为如果diff>0,那么最小值就是当前的minx
怎么top？
- 如果diff<0，那么说明当前就是最小值，top就是minx
- diff>0，就需要还原当前值，x=minx(diff>0，说明当前的minx是上一个minx，是相同值)+diff

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack=[]   # store diff with currentMinX
        self.minx=0  # currentMinX
        self.diff=0  # diff with currentMinX



    def push(self, x: int) -> None:
        self.diff=x-self.minx
        if self.diff <0 or not self.stack: self.minx=x  #细节1
        # self.minx=x if self.diff<0 else
        if not self.stack: self.stack.append(0) #细节1
        else:
            self.stack.append(self.diff)


    def pop(self) -> None:
        popdiff=self.stack.pop()
        if popdiff<=0:
            self.minx=self.minx-popdiff 



    def top(self) -> int:
        return self.minx if self.stack[-1]<0 else self.minx+self.stack[-1]  #如果当前就是最小值（diff<0），那么就直接返回最小值；如果不是，那么还原当前值；细节2


    def getMin(self) -> int:
        return self.minx



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

0 赞同 0 条回复

yelinliner 普通 2024年12月9日上午11:33

stack 栈中，不能存放原始数值，而是应该存放差值，啥差值？就是存放栈顶与最小值的差值

辅助值：最小值 min 不需要辅助栈

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 sub = x - min;
            // 如果差值小于0，显然 x 成为最小值，否则最小值不变
            min = sub < 0 ? x : min;
            stack.push(sub);
        }
    }

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

    public int getMin() {
        return min;
    }
 }

0 赞同 0 条回复

岱永久会员 2024年12月4日下午8:23

稍微有点难理解，多做几遍

class MinStack{
    Stack<Long> stack;
    Long min;

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

    }

    public void push(int x){
        if(stack.isEmpty()){
            stack.push(0l);
            min = Long.valueOf(x);
        }else{
            stack.push((long)(x-min));
            min = Math.min(x,min);
        }

    }

    public void pop(){
        if(stack.peek() < 0){
            min = min - stack.pop();
            return;
        }
        stack.pop();
    }

    public int  top(){
        if(stack.peek() > 0){
            return (int)(min + stack.peek());
        }else{
            return Math.toIntExact(min);
        }

    }

    public int getMin(){
        return Math.toIntExact(min);
    }


}

0 赞同 0 条回复

陆狗陆狗普通 2024年11月30日下午9:52

为什么要这样做？相当于通过stack的值（放的差额）去间接保存上一个最小值的信息
当stack的值<0，说明当前元素就是最小值，当前元素的实际值=min
当stack的值>0，说明当前元素不是最小值，当前元素的实际值=min+stack值

class MinStack {

    // 【错误点】，没有定义泛型的类型
    private Stack<Integer> normalStack;
    private Integer min;

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

    public void push(int x) {
        if(normalStack.isEmpty()){
            // 【错误点1,第一个点的设置】
            normalStack.push(0);
            min=x;
        }else{
            // 比较当前值和最小值的关系，存放的也是gap
            int gap=x-min;
            normalStack.push(gap);
            min=gap<0?x:min;
        }
    }

    public void pop() {
        if(normalStack.peek()<0){
            // 【错误点2】
            min=min-normalStack.peek();
        }
        normalStack.pop();
    }

    public int top() {
        if(normalStack.peek()<0){
            return min;
        }else{
            return normalStack.peek()+min;
        }
    }

    public int getMin() {
        return min;
    }
}

0 赞同 0 条回复

迢迢星野普通 2024年11月29日下午3:10

    /**
     * 最小栈的最优解
     *      时间复杂度为 O(1), 空间复杂度也为 O(1)，
     * 使用一个数来表示最小值，那么在最小值就是栈顶元素时，出栈时，如何获取下一个的最小值呢？
     *  栈顶元素
     */
    class MinStack {
        Stack<Integer> stack;
        //Stack<Integer> min;
        int min;

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

        public void push(int x) {
            if (stack.empty()) {
                min = x;
                stack.push(x);
            }else {
                // 入栈的是 栈顶元素 - 最小值
                int compare = x - min;
                stack.push(compare);
                // 更新最小值，什么时候更新呢？当 x < min 时
                min = compare < 0 ? x : min;
            }
        }

        public void pop() {
            // 出栈
            int top = stack.peek();
            // 更新最小值
            min = top < 0 ? (min - top) : min;
            stack.pop();
        }

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

        public int getMin() {
            return min;
        } 
    }

思路：栈中存储的是差值，而不是元素本身，一个变量用来存储最小值。
时间复杂度：O(1)。
空间复杂度：O(1)。

0 赞同 0 条回复

Tom Yuan 普通 2024年11月28日上午2:57

方法额外用一个值记录最小值，push时将差值push进stack，pop时将原有值还原，并且如果不是之前的最小值，就同时还原之前的最小值。

class MinStack:
    def __init__(self):
        self.min = 0
        self.stack = []

    def push(self, x):
        if not len(self.stack):
            self.min = x
            self.stack.append(x - self.min)
        else:
            compare = x - self.min
            self.stack.append(compare)
            if compare < 0:
                self.min = x

    def pop(self):
        if not len(self.stack):
            return
        diff = self.stack[-1]
        if diff < 0:
            self.min = self.min - diff
        return self.min - diff

    def getMin(self):
        return self.min

stack = MinStack()
stack.push(3)
stack.push(5)
print(stack.getMin())  # 输出 3
stack.push(2)
stack.push(1)
print(stack.getMin())  # 输出 1
stack.pop()
print(stack.getMin())  # 输出 2
stack.pop()
print(stack.getMin())  # 输出 3

time O(1) space O(1)
与此同时 leetcode还有一个用链表的处理还没完全理解贴个链接
https://leetcode.com/problems/min-stack/solutions/49010/clean-6ms-java-solution/

0 赞同 0 条回复

生活在经验里普通 2024年11月27日下午3:51

type MinStack struct {
    stack []int
    min   int
}

func Constructor() MinStack {
    return MinStack{stack: []int{}}
}

func (this *MinStack) Push(x int) {
    if len(this.stack) == 0 {
        this.min = x
        this.stack = append(this.stack, 0) // 第一个元素，差值为0
    } else {
        compare := x - this.min
        this.stack = append(this.stack, compare)
        if compare < 0 {
            this.min = x // 更新最小值
        }
    }
}

func (this *MinStack) Pop() {
    if len(this.stack) == 0 {
        return // 防止栈为空时调用pop
    }
    top := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    if top < 0 {
        this.min = this.min - top // 恢复旧的最小值
    }
}

func (this *MinStack) GetMin() int {
    return this.min
}

func main() {
    minStack := Constructor()
    minStack.Push(2)
    minStack.Push(1)
    minStack.Push(3)
    minStack.Push(0)
    fmt.Println(minStack.GetMin()) // 输出最小值 0
    minStack.Pop()
    fmt.Println(minStack.GetMin()) // 输出最小值 1
    minStack.Pop()
    fmt.Println(minStack.GetMin()) // 输出最小值 1
    minStack.Pop()
    fmt.Println(minStack.GetMin()) // 输出最小值 2
}

0 赞同 0 条回复

越努力越幸运普通 2024年11月26日下午11:15

参考评论区小伙伴的写法

class MinStack {
public:
    /** initialize your data structure here. */
    stack stk; // 存储入栈元素和与最小值的差值
    int minVal; // 存储当前栈内元素的最小值
    MinStack() {

    }

    void push(int x) {
        if(!stk.empty()) {
            int diff = x - minVal;
            if(diff < 0) {
                minVal = x; // 差值小于 0, 更新最小值
            }
            stk.push(diff);
        } else {
            // 栈为空，最小值更新为第一个入栈元素，差值为 0, 入栈
            minVal = x;
            stk.push(0);
        }
    }

    void pop() {
        if(stk.top() < 0) {
            minVal = minVal - stk.top();
        }
        stk.pop();
    }

    int top() {
        if(stk.top() < 0) {
            //在入栈时，diff 小于 0, 将原元素 x 更新为最小值
            //所以此时真正的栈顶元素就是最小值
            return minVal;
        }
        return minVal + stk.top(); // x = diff + minVal;
    }

    int getMin() {
        return minVal;
    }
};

0 赞同 0 条回复

lQl 永久会员 2024年11月25日下午10:23

关键在于记录栈中元素和最小值之间的关系,能够在弹出最小元素时回退到之前最小的元素

class MinStack {
    private long min; // 用于存储当前栈中的最小值
    private java.util.Stack<Long> stack; // 用于存储差值

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

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0L); // 当栈为空时，存储 0
            min = x;        // 更新最小值
        } else {
            long diff = x - min; // 计算差值
            stack.push(diff);
            if (diff < 0) {
                min = x; // 更新最小值为新的更小值
            }
        }
    }

    public void pop() {
        if (stack.isEmpty()) {
            return;
        }
        long top = stack.pop();
        if (top < 0) {
            // 如果差值小于 0，说明弹出的元素是当前最小值
            min = min - top; // 恢复上一个最小值
        }
    }

    public int top() {
        if (stack.isEmpty()) {
            throw new java.util.EmptyStackException();
        }
        long top = stack.peek();
        if (top < 0) {
            // 如果差值小于 0，当前元素就是最小值
            return (int) min;
        } else {
            // 如果差值非负，返回 min + 差值
            return (int) (min + top);
        }
    }

    public int getMin() {
        if (stack.isEmpty()) {
            throw new java.util.EmptyStackException();
        }
        return (int) min;
    }
}

0 赞同 0 条回复

Kisara 普通 2024年11月25日下午7:46

没有思路，这是我看的gpt的解法，基本和帅地给的一样，算是大彻大悟了都是O（1）

public class MinStack {
    private long minValue; // 当前最小值
    private java.util.Stack<Long> stack; // 存储差值的栈

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

    // push操作
    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0L); // 初始值，差值为0
            minValue = x;   // 更新最小值
        } else {
            stack.push(x - minValue); // 存储差值
            if (x < minValue) {
                minValue = x; // 更新最小值
            }
        }
    }

    // pop操作
    public void pop() {
        if (stack.isEmpty()) {
            return;
        }
        long top = stack.pop();
        if (top < 0) {
            // 如果差值为负，说明移除的值是当前最小值
            minValue -= top; // 恢复之前的最小值
        }
    }

    // 获取栈顶元素
    public int top() {
        long top = stack.peek();
        if (top > 0) {
            // 正值，栈顶是 minValue + 差值
            return (int) (minValue + top);
        } else {
            // 负值，栈顶是 minValue
            return (int) minValue;
        }
    }

    // 获取最小值
    public int getMin() {
        return (int) minValue;
    }

    // 测试代码
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(3);
        minStack.push(1);
        minStack.push(2);
        System.out.println(minStack.getMin()); // 输出 1
        minStack.pop();
        System.out.println(minStack.getMin()); // 输出 1
        minStack.pop();
        System.out.println(minStack.getMin()); // 输出 3
    }
}

0 赞同 0 条回复

Renasc 普通 2024年11月25日下午7:34

待理解

public class {

    private Stack stack = new Stack();
    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;
    }
 }

0 赞同 0 条回复

Pendulumpal 普通 2024年11月25日下午6:21

关键在记录每个元素与最小值间的差值

“`c++
class MinStack {
public:
/** initialize your data structure here. */
stacksk;
long long minn;
MinStack() {

}

void push(long long x) {
    if(sk.empty()){
        sk.push(0);
        minn=x;
    }else{
        sk.push((x-minn));
        minn=min(x,minn);
    }
}

void pop() {
    if(sk.top()<0){
        minn=minn-sk.top();
    }
    sk.pop();
}

long long top() {
    if(sk.top()<0)return (int)minn;
    else return (int)(sk.top()+minn);
}

long long getMin() {
    return minn;
}

};

“`

0 赞同 0 条回复

jaron 普通 2024年11月25日下午6:14

时间复杂度：O(1)
额外空间复杂度：O(1)
看了文章的做法，妙啊！加上了top方法，用int跑力扣上的这道题好像会越界，改成了long

class MinStack {

    private final Stack<Long> stack = new Stack<Long>();
    private long min;

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

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

    public int top() {
        long top = stack.peek();
        long add = top < 0 ? (min - top) : min;
        return (int) (top + add);
    }

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

0 赞同 0 条回复

无言永久会员 2024年11月25日下午4:06

class MinStack {
public:
    /** initialize your data structure here. */
    stack stk; // 存储入栈元素和与最小值的差值
    int minVal; // 存储当前栈内元素的最小值
    MinStack() {

    }

    void push(int x) {
        if(!stk.empty()) {
            int diff = x - minVal;
            if(diff < 0) {
                minVal = x; // 差值小于 0, 更新最小值
            }
            stk.push(diff);
        } else {
            // 栈为空，最小值更新为第一个入栈元素，差值为 0, 入栈
            minVal = x;
            stk.push(0);
        }
    }

    void pop() {
        if(stk.top() < 0) {
            minVal = minVal - stk.top();
        }
        stk.pop();
    }

    int top() {
        if(stk.top() < 0) {
            //在入栈时，diff 小于 0, 将原元素 x 更新为最小值
            //所以此时真正的栈顶元素就是最小值
            return minVal;
        }
        return minVal + stk.top(); // x = diff + minVal;
    }

    int getMin() {
        return minVal;
    }
};

0 赞同 0 条回复

月下足迹普通 2024年11月25日下午2:29

//gpt给出的答案，供学习参考
//差值编码法

class MinStack2 {
Stack stack; // 使用一个栈存储差值编码
long minnum; // 当前的最小值

    /** initialize your data structure here. */
    public MinStack2() {
        stack = new Stack<>();
        minnum = 0;
    }

    public void push(int x) {
        if (stack.isEmpty()) {
            // 栈为空时，直接存储元素，并更新最小值
            minnum = x;
            stack.push(0L); // 存储与最小值的差值
        } else {
            // 存储当前值相对于最小值的差值
            stack.push((long)x - minnum);
            // 如果当前值小于最小值，更新最小值
            if (x < minnum) {
                minnum = x;
            }
        }
    }

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

        long diff = stack.pop();
        if (diff < 0) {
            // 如果差值小于 0，说明弹出的元素是当前最小值
            // 需要恢复前一个最小值
            minnum = minnum - diff;
        }
    }

    public int top() {
        long diff = stack.peek();
        if (diff > 0) {
            // 如果差值大于 0，当前栈顶值为 minnum + diff
            return (int)(minnum + diff);
        } else {
            // 如果差值小于等于 0，当前栈顶值为 minnum
            return (int)minnum;
        }
    }

    public int getMin() {
        return (int)minnum; // 直接返回当前最小值
    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年11月25日上午11:50

思路：需要一个栈完成栈的常规操作和一个min变量记忆当前最小值，看了文章解析，手动模拟一下过程就懂了。

class MinStack {
   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);
            min = compare < 0 ? x : min;
        }
    }

    public void pop() {
        int top = stack.peek();
        min = top < 0 ? (min - top) : min;
        stack.pop();
    }
     public int top() {
        if (stack.peek() < 0) return (int) min;
        else return (int) (stack.peek() + min);
    }


    public int getMin() {
        return min;
    }
}

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【基本数据结构】变形题：最小栈的最优解

共以下 16 个回答

# 回答此问题 取消回复

# 回答此问题取消回复