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

本问题对应课程链接：剑指offer刷题第五期

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

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

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

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

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

shuaidi

更新于 3 年前 318 15

共以下 15 个回答

QQiing 普通 2023年9月4日下午9:50

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

}

void push(int x) {
    s1.push(x);
    if(s2.empty() || x <= s2.top())
    {
        s2.push(x);
    }
}

void pop() {
    if(!s1.empty())
    {
        if(s1.top() == s2.top())
        {
            s2.pop();
        }
        s1.pop();
    }
}

int top() {
    if(!s1.empty())
    {
        return s1.top();
    }
    return 0;
}

int min() {
    if(!s2.empty())
    {
        return s2.top();
    }
    return 0;
}

private:
stack s1, s2;
};
时间复杂度为O（1）

0 赞同 0 条回复

Miracle· 普通 2023年8月26日下午10:32

差值栈，注意数值范围的限制

0 赞同 0 条回复

登录以回复

Marc 普通 2023年8月21日上午12:27

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.minVal = 0

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

    def pop(self) -> None:
        top = self.stack.pop()
        if top < 0:
            self.minVal -= top 

    def top(self) -> int:

        return self.minVal if self.stack[-1] < 0 else self.minVal + self.stack[-1]

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

参考大佬的思路，栈内存差值元素

0 赞同 0 条回复

辰北、普通 2023年8月20日下午5:17

//双栈加一个min——value;记录最小值，需要时调用；

0 赞同 0 条回复

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

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

0 赞同 0 条回复

登录以回复

木木普通 2023年8月19日下午4:01

時間複雜度O(1)空間複雜度O(1)
利用push時儲存最小值和當前值的差值, 並且同步更新最小值來確保調用getmin函數時可以正確取得棧中的最小值


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

    }

    stack s;
    long long min_val = 0;

    void push(int x) {
      if (s.empty()) {
        min_val = x;
        s.push(0);
      }
      else {
        long long delta = x - min_val;
        s.push(delta);
        min_val = delta < 0 ? x : min_val;
      }
    }
    
    void pop() {
      if (!s.empty()) {
        if ( s.top() < 0) {
        min_val = min_val - s.top();
        }
        s.pop();
      }
    }
   
    int top() {
        if (s.top() > 0) {
          return s.top() + min_val;
        }
        else {
          return min_val;
        }
    }
    int min() {
      return min_val;
    }
};

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月19日下午2:35

使用差值栈

class MinStack {

    Stack<Long> stack;
    Long min;

    /** initialize your data structure here. */
    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 min() {
        return Math.toIntExact(min);
    }
}

0 赞同 0 条回复

Jou Siankwa 普通 2023年8月18日下午10:33

class MinStack {
    /** initialize your data structure here. */

    Stack<Long> stack;
    long minValue;
    public MinStack() {
        stack = new Stack<>();
        minValue = 0;
    }

    public void push(int x) {
        if(stack.isEmpty()){
            stack.push(0L);
            minValue = x;
        }else{
            long l = x - minValue;
            stack.push(l);
            if(l < 0){
                minValue = x;
            }
        }
    }

    public void pop() {
        if(stack.peek() > 0){
            stack.pop();
        }else {
            minValue -= stack.pop();
        }
    }

    public int top() {
        if(stack.peek() > 0){
            long l = minValue + stack.peek();
            return (int) l;
        }else{
            return (int) minValue;
        }
    }

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

}

用栈保存当前值与最小值的差值。如果当前值是最小值，更新最小值。

0 赞同 0 条回复

一个人的风海吹了两遍普通 2023年8月18日下午4:44

/*
* 两个栈实现 获得栈中最小元素
* */
package stack;

import java.util.Stack;

class stack {

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public stack() {
        this.stack1 = new Stack();
        this.stack2 = new Stack();
    }

    //进栈
    public void push(int x) {
        if(stack1.isEmpty()){
            stack1.push(x);
            stack2.push(x);
        }else {
            stack1.push(x);
            if (stack1.peek() <= stack2.peek())
                stack2.push(x);
        }
    }
    //出栈
    public void pop() {
        if(stack2.peek().intValue()==stack1.peek().intValue()){
            stack2.pop();
            stack1.pop();
        }else {
            stack1.pop();
        }
    }
    //获得栈顶元素
    public int top() {
        return stack1.peek();
    }
    //获得栈中最小值
    public int min() {
        return stack2.peek();
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月17日下午9:35

class MinStack {
private:
    // 栈保存当前元素和最小值minVal的差值
    stack<long long> stk;
    long long minVal;
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        if(stk.empty()){
            stk.push(0);
            minVal = x;
        }
        else{
            stk.push(x - minVal);
            if(x < minVal) minVal = x;
        }
    }

    void pop() {
        // 如果栈顶元素小于0，说明当前元素比之前的元素小
        // 该元素要出栈了，更新minval
        if(!stk.empty()){
            if(stk.top() < 0){
                minVal -= stk.top();
            }
            stk.pop();
        }
    }

    int top() {
        if(stk.top() > 0){
            return stk.top() + minVal;
        }
        else{
            return minVal;
        }
    }

    int min() {
        return minVal;
    }
};

0 赞同 0 条回复

逸兴遄飞普通 2023年8月17日上午9:59

保存差值法，不需要使用额外的栈。

class MinStack {

    Stack stack;
    Long min;

    /** initialize your data structure here. */
    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 min() {
        return Math.toIntExact(min);
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年8月16日下午10:26

// 时间O(1),空间O(1)
class MinStack {
    stack<int> stk;
    int min;
public:
    MinStack() {

    }

    void push(int val) {
        if(stk.empty())
        {
            min = val;
            stk.push(0);
        }
        else
        {
            int diff = val - min;
            if(diff<0)
            {
                min = val;
            }
            stk.push(diff);
        }
    }

    void pop() {
        int val = stk.top();
        stk.pop();
        if(val<0)
        {
            min = min -val;
        }
    }

    int top() {
        int val = stk.top();

        return val<0?min:min+val;
    }

    int getMin() {
        return min;
    }
};

0 赞同 0 条回复

c 普通 2023年8月16日下午5:04

记录差值

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

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

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

    public int min() {
        return min;
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年8月16日下午5:03

1、一个栈实现
···java
class MinStack {

Stack<Integer> stack;
int min;

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

public void push(int x) {
    stack.push(min);
    min = Math.min(x, min);
    stack.push(x);
}

public void pop() {
    stack.pop();
    min = stack.pop();
}

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

public int min() {
    return min;
}

}

“`

0 赞同 0 条回复

Vince 普通 2023年8月16日下午4:19
// 单min变量法
// 无辅助栈
// data = x – min
// if x < min:
// data = min – oldMin
// oldMin = min – data
class MinStack {
long min;
Stack s;
/** initialize your data structure here. */
public MinStack() {
s = new Stack<>();
}
```
public void push(int x) {
    if(s.isEmpty()){
        s.push(0L);
        min = x;
    }else{
        s.push(x - min);
    }
    min = Math.min(x, min);
}

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

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

public int min() {
    return (int)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.min();
*/
0 赞同 0 条回复

登录以回复

# 回答此问题取消回复

后才能回答

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

共以下 15 个回答

# 回答此问题 取消回复

# 回答此问题取消回复