当前位置：
  1. 首页
  2. 剑指offer刷题第六期
  3. 问题详情

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

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

要求：

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

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

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

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

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

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

shuaidi
359 20

共以下 20 个回答

  • Laboratory 普通 2024年4月15日 下午11:43

    利用差值存入栈中可以保证O（1）的空间复杂度

    0 赞同 0 条回复
  • YOLO 普通 2024年3月14日 上午11:40 
    /*实现一个这样的栈，这个栈除了可以进行普通的push、pop操作以外，还可以进行getMin的操作，getMin方法被调用后，会返回当前栈的最小值。栈里面存放的都是 int 整数，并且数值的范围是 [-100000, 100000]。要求所有操作的时间复杂度是 O(1)。*/  

pubilc class 设计一个有gitMin的栈{
    Stack<Integer>stack = new Stack();
    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;
            if(min < 0>){
                min = x;
            }
        }
    }
    public void pop(){
        int top = stack.peek();
        // 如果top小于0，显然最小值也一并会被删除，此时更新最小值
        min = top < 0?(min - top):top;    //????
        stack.pop();
    }
    public int getMin(){
        return min;
    }
}
    0 赞同 0 条回复
  • 晚风、 普通 2024年3月13日 上午12:34

    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:
    stack,i = [],0
    for num in putIn:
    stack.append(num)
    while stack and stack[-1] takeOut[i]:
    stack.pop()
    i = i+1

        return not stack

    通过辅助栈存储栈元素非严格从大到小排列元素

    0 赞同 0 条回复
  • kfaebot 普通 2024年3月12日 下午4:21 
    class MinStack {
public:
    stack<long long> main_stack; //栈中存的是差值
    long long diffval; //当前最小值

    MinStack() {

    }

    void push(int val) {
        if(main_stack.empty()){
            main_stack.push(0); //若栈为空，差值0入栈（元素本身减本身）
            diffval=(long long)val; //当前最小值为输入元素
        }
        else{
            main_stack.push((long long)val-diffval); //差值入栈
            diffval=min((long long)val,diffval); //更新当前最小值
        }
    }

    void pop() {
        if(main_stack.empty()){
            return;
        }
        if(main_stack.top()<0){
            diffval=diffval-main_stack.top();
        }
        main_stack.pop();

    }

    int top() {
        if(main_stack.top()<0){
            return (int)diffval;
        }
        else{
            return (int)main_stack.top()+diffval;
        }
    }

    int getMin() {
        return (int)diffval;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
    0 赞同 0 条回复
  • Fancy 普通 2024年3月12日 上午7:56

    class MinStack:
    # 1个栈，栈里只记录 cur-minNum，即存放每个数字和最小值的差
    def init(self):
    self.stack = []
    self.root = -1
    self.minNum = -1
    def push(self, x: int) -> None:
    if not self.stack:
    self.stack.append(0)
    self.root = x
    self.minNum = x
    else:
    self.stack.append(x-self.minNum) #如果x<minNum，那么存入的是负数
    if x < self.minNum:
    self.minNum = x
    def pop(self) -> None: #难点：如何找回前面记录的最小值
    x = self.stack.pop()
    # self.minNum = 原min + x
    if x < 0:
    self.minNum -= x

    def top(self) -> int: #对应的top也要做相应修改！！！
    top = self.stack[-1]
    if top < 0:
        return self.stack[-1] + (self.minNum - top)
    return self.stack[-1] + self.minNum

def getMin(self) -> int:
    return self.minNum
    0 赞同 0 条回复
  • 一颗红豆 普通 2024年3月11日 下午2:03

    直接将最小值信息存到栈中，核心就是如何在最小值出栈后能合理更换最小值 通过存差的方式 差为负值则最小值更新
    class MinStack {
    public:
    /** initialize your data structure here. */
    stack s1;
    int min;
    MinStack() {
    std::stack     s1;
    min = 0;

    }

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

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

int top() {
    return s1.top()<0?min:min+s1.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();
    */

    0 赞同 0 条回复
  • e=mc² 普通 2024年3月10日 下午10:39

    差值栈 pop和top方法返回的值无法保证正确

    0 赞同 0 条回复
  • 莫～慢～待 普通 2024年3月10日 上午12:55

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

    public void push(int x) {
if(zhan.isEmpty())
{
zhan.push(0L);
minValue=Long.valueOf(x);
}
else
{
Long longvalue=(long)x;
zhan.push(longvalue-minValue);
minValue=(longvalue-minValue)>0?minValue:longvalue;
}
}

public void pop() {
long top=zhan.peek();
zhan.pop();
minValue=top>0?minValue:minValue-top;
}

public int top() {
long top=zhan.peek();
return top>0?(int)(minValue+top):Math.toIntExact(minValue);
}

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

    }
    维护一个记录当前插入值和最小值的差距值的栈，注意防止数据溢出

    0 赞同 0 条回复
  • 零 普通 2024年3月9日 下午9:18

    思路：参考解析，神奇
    代码：

    
    class MinStack {
        Stack stack;
        Integer minDifference;

        public MinStack() {
            stack = new Stack<>();
            minDifference = Integer.MIN_VALUE;
        }

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

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


        public int top() {
            return stack.peek() < 0 ? minDifference : minDifference-stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }
    0 赞同 0 条回复
  • 白雪公主倒拔垂杨柳 永久会员 2024年3月9日 下午3:37

    滴滴

    0 赞同 0 条回复
  •     普通 2024年3月7日 下午8:14

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

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

void pop() {
    if(stk1.top()==stk2.top())
        stk2.pop();
    stk1.pop();
}

int top() {
    return stk1.top();
}

int getMin() {
    return stk2.top();
}

    };
    时间O（1） 空间 O(n)

    1 赞同 0 条回复
  • 紫芝 普通 2024年3月7日 上午8:56

    谢谢，获得新解法：时空复杂度都是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();
    */

    “`

    0 赞同 0 条回复
  • NULL 普通 2024年3月6日 下午11:22

    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 条回复
  • Jankin 普通 2024年3月6日 下午8:54 
    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;
    }
 }

    时间复杂度：O（1）
    空间复杂度：O（1）

    0 赞同 0 条回复
  • 云无深雁影 普通 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();
    */

    0 赞同 0 条回复
  • Jimmy 普通 2024年3月6日 下午6:27

    使用差值栈，对存储的值的范围有要求

    class MinStack {
private:
    stack<int> stack;
    int min;
public:
    /** initialize your data structure here. */
    MinStack() {

    }

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

    void pop() {
        /* 最小值在哪里：
        1.在push的时候，min不断更新，永远保存最小值 
        2.在pop的时候，若栈顶那个差值>0，说明该差值对应的元素>min，则不更新min；
                       若栈顶那个差值<0，说明该差值对应的元素就是min，则要更新min，
        3.如何更新_min:在插入栈顶这个差值(_top)对应的元素之前，最小值为_premin,插入之后最小值为min，
                        top = min - premin,则_premin = min - top
        */
        int top = stack.top();
        min = top < 0 ? min-top : min;
        stack.pop();
    }

    int top() {
        return stack.top() < 0 ? min : min + stack.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();
 */
    0 赞同 0 条回复
  • heathhou 普通 2024年3月6日 下午1:43 
    class MinStack {
public:
    stack<long> s;
    long min;
    /** initialize your data structure here. */
    MinStack() {

    }

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

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

    int top() {

        if(s.top() < 0){
            // 这个元素压入栈的时候，min被更新了，而且就是被这个元素更新的。所以此时栈顶元素就是min
            return min;

        }else{
            // 这个元素压入栈的时候，min没有被更新
            // 此时栈顶元素是： x - min
            return s.top() + min;
        }
    }

    int getMin() {
        return min;
    }
};
    0 赞同 0 条回复
  • mpweixin用户 普通 2024年3月6日 下午1:37

    差值栈 防止数据溢出

    0 赞同 0 条回复
  • Thaddeus 永久会员 2024年3月6日 上午11:17

    差值栈

    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; // 存放当前栈中最小的元素
    
};
    0 赞同 0 条回复
  • 言之命至 普通 2024年3月5日 下午9:13 
    public class 设计一个有gitMin的栈 {

    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;// 注意：一定是先压入，在更新，因为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;
    }
 }

    时空复杂度：O（1）

    0 赞同 0 条回复

# 回答此问题

后才能回答