宁永久会员 2023年3月16日下午5:35

用这种方法重新提交了一下最小栈问题，有一个测试用例存在溢出问题，需要用long存储

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

    public void push(int x) {
        if(stack.isEmpty()){
            stack.push(0L);
            min = x;
        }else{
            stack.push(x - min);
            if(x - min < 0){
                min = x;
            }
        }
    }
    public void pop() {
        long top = stack.peek();
        if(top < 0){
            min = min - top;
        }
        stack.pop();
    }
    public int top() {
        if(stack.peek() > 0){
            return Math.toIntExact(stack.peek() + min);
        }
        return Math.toIntExact(min);
    }
    public int min() {
        return Math.toIntExact(min);
    }
}

0 赞同 0 条回复

lucca 普通 2022年12月31日下午9:02

照着打，还是挺难理解的

class MinStack {

    // cur_min
    long min;
    // s[i] cur_num - last_min
    long[] s = new long[20010];
    int top = -1;

    // cur_num ≥ last_min       cur_num ≥ last_min
    //         ↓                        ↓
    //      sub ≥ 0                  sub < 0
    //         ↓                        ↓
    // cur_min = last_min       cur_min = cur_num

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

    public void push(int x) {
        if (top == -1) {
            min = x;
            s[++top] = 0;
        } else {
            long sub = x - min;
            if (sub < 0) min = x;
            s[++top] = sub;
        }
    }

    public void pop() {
        if (s[top] < 0) min -= s[top];
        top--;
    }

    public int top() {
        // last_min < 0  -> cur_min = cur_num
        if (s[top] < 0) return (int) min;
        // last_min >= 0 -> cur_min = last_min -> cur_num = last_min + sub
        return (int) (min + s[top]);
    }

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

0 赞同 0 条回复

努力刷题普通 2022年12月5日上午3:54

辅助栈存与最小值的差值
class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.minx = 1e5


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        if not self.stack:
            self.minx = x
        self.stack.append(x - self.minx)
        if x - self.minx < 0:
            self.minx = x


    def pop(self):
        """
        :rtype: None
        """
        if self.stack[-1] < 0:
            self.minx = self.minx - self.stack[-1]
        self.stack.pop()


    def top(self):
        """
        :rtype: int
        """
        if self.stack[-1] > 0:
            return self.stack[-1] + self.minx
        return self.minx


    def min(self):
        """
        :rtype: int
        """
        return self.minx

0 赞同 0 条回复

派大星普通 2022年12月2日下午9:07

class MinStack {
//时间复杂度O（n）
    private Stack<Integer> stack;
    private int min;
    public MinStack() {
        stack = new Stack<>();
    }
    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(0);
            min = val;
        } else {
            int compare = val - min;
            stack.push(compare);
            min = compare < 0 ? val : min;
        }
    }
    public void pop() {
        int topValue = stack.peek();
        min = topValue < 0 ? (min - topValue) : min;
        stack.pop();
    }
    public int getMin() {
        return min;
    }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年12月2日下午4:13

    /**
     * 最优解法
     * 入栈
     */
    public static void push(int x) {
        if (stack.isEmpty()) {
            min = x;
            stack.push(0);
        } else {
            int num = x - min;
            stack.push(num);
            min = num < 0 ? x : min;
        }
    }

    public static void pop() {
        int top = stack.peek();
        min = top < 0 ? (min - top) : min;
        stack.pop();
    }
    //获取最小值
    public static int getMin(){
        return min;
    }

0 赞同 0 条回复

PatNick 普通 2022年12月2日下午3:12

# 方法1：时间复杂度O(1),空间复杂度O(n)：添加一个辅助栈存放当前的最小值
class Mystruck():
    def __init__(self):
        self.help_list = []
        self.cur_list = []

    def push(self,value):
        self.cur_list.append()

        # 当压入新的数字时，也要更新当前的最小值
        if len(self.help_list) == 0:
            self.help_list.append(value)

        else:
            self.help_list.append(min(self.help_list[-1],value))

    def pop(self):
        if len(self.cur_list) == 0:
            return None
        else:
            self.help_list.pop()
            return self.cur_list.pop()

    def getMin(self):
        return None if len(self.help_list) == 0 else self.help_list[-1]



# 方法2，时间复杂度O(1),空间复杂度O(1),栈中存放的是栈顶和最小值之间的差值
class Mystruck1():
    def __init__(self):
        self.min_value = 0
        self.list = []


    def push(self,value):
        if len(self.list) == 0:
            self.min_value = value
            self.list.append(0)
        else:

            self.list.append(value-self.min_value)
            # 如果添加的值与之前的最小值的差小于1，说明当前添加的更小，需要更新最小值
            self.min_value = value if value-self.min_value < 0 else self.min_value


    def pop(self):
        # 如果差值小于0说明更换过最小值
        self.min_value = self.min_value - self.list[-1] if self.list[-1] < 0 else self.min_value

    def getMin(self):
        return self.min_value

0 赞同 0 条回复

如梦似歌普通 2022年11月14日下午8:54

只使用一个栈，栈中存放的是存放栈顶与最小值的差值

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

0 赞同 0 条回复

cute. 普通 2022年11月4日上午9:49

只使用一个stack栈，stack里面不存放原始数值，而是差值。差值=arr[i]-min

var MinStack = function() {
    this.stack = [];
    var min;
}
MinStack.proyptype.push = function() {
    if(stack.isEmpty()) {
        min = x;
        stack.push(0);
    } else {
        // 计算差值
        var compare = x - min;
        stack.push(compare);
        // 如果差值小于0，显然x成为最小值，否则最小值不变
        min = compare < 0 ? x : min;
    }
}
MinStack.prototype.pop = function() {
    let top = stack.peek();
    // 如果top小于0，显然最小值也会一并被删掉，此时更新最小值
    min = top < 0 ? (min - top) : min;
    stack.pop();
}
MinStack.prototype.getMin = function() {
    return min;
}

时间复杂度:O(1)
空间复杂度:O(1)
此解法前提：数值范围有限制，然么会溢出

0 赞同 0 条回复

Asphyxia 普通 2022年11月1日下午10:00

感觉思路来自差分数组，用一个基准和差分数组可以恢复原数组
当然本题min并不单纯是一个基准，不过也是可以恢复出原始栈的

0 赞同 0 条回复

小肸永久会员 2022年11月1日下午5:31

之前实现最小栈，用来额外的一个栈min来存放最小值，其实栈min中可能有一些重复的最小值，可以在入栈和出栈出判断是否需要更新最小值来更新最小栈，以此减少一下空间开销。我面试时估计也只能想到这种优化，对于将int型的4个字节拆分为2个字节、2个字节使用，只能用于小范围的数值。最优解是利用数值差，栈中差值，栈顶元素和最小值的差值。当这样只能得到栈中的最小值，栈顶的元素无法获取，也符合题目要求。

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

0 赞同 0 条回复

cxxz 普通 2022年11月1日下午3:07

没有思路，参考帅老师的解析。
对min从上至下标记，min0, min1···。以pop最后一个为例，当 top < 0 时，即要pop的元素是最小值，那么 min0=x，x-min1=top，所以更新后的最小值 min1 = min0-top，否则min不变。

“`cpp
class MinStack {
public:
/** initialize your data structure here. */
stack sk_min;
int min;
MinStack() {

}

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

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

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

int getMin() {
    return min;
}

};
cpp

0 赞同 0 条回复

马啸天永久会员 2022年10月31日下午4:32

//注意，第一个方法要有取值范围限制，int差值取值必须在 [-2147483648，2147483647]
public class MinStack {

    private Stack<Integer> stack;
    private int min;

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

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

    public void pop() {
        int top = stack.peek();
        int num = stack.pop();
        if (top >= 0)
            System.out.println("弹出值为" + (top + min));
        else {
            System.out.println("弹出值为" + min);
            min = min - num;
        }

    }

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

    public int min() {
        return min;
    }
}

class MinStack1 {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MinStack1() {
        stack1 = new Stack();
        stack2 = new Stack();
    }

    public void push(Integer x) {

        stack1.push(x);
        if (stack2.isEmpty() || x <= stack2.peek()) {
            stack2.push(x);
        }
    }

    public Integer pop() {

        if (stack1.isEmpty()) {
            return null;
        }
        if (stack1.peek() == stack2.peek())
            stack2.pop();
        return stack1.pop();

    }

    Integer getMin() {
        return stack2.isEmpty() ? null : stack2.peek();
    }
}

0 赞同 0 条回复

symbol 普通 2022年10月31日上午10:07

var min_num int

type MinStack struct {
    stack []int

}

/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{}
}


func (this *MinStack) Push(x int)  {
    if len(this.stack) == 0{
        this.stack = append(this.stack, x)
    }else {
        min_num = x
    }
    temp := min_num - x //计算差值
    this.stack = append(this.stack, temp)
    if temp < 0 {
        min_num = x
    }
}


func (this *MinStack) Pop()  {
    top := this.stack[len(this.stack)-1] //取出栈顶元素
    this.stack = this.stack[:len(this.stack)-1] //更新栈元素
    //若栈顶元素小于0 则需要更新最小值
    if top < 0 {
        min_num = min_num-top
    }
}


func (this *MinStack) Min() int {
    return min_num
}

0 赞同 0 条回复

cxc 普通 2022年10月30日下午2:28

class MinStack {

    private Stack<Long> stack;
    private long min;
    public MinStack() { 
        stack = new Stack<>();
    }

    public void push(int val) {
         if (stack.isEmpty()) {
            min = val;
            stack.push(0L);
        } else {
            // 计算差值
            long compare = (long)val - min;
            stack.push(compare);
            // 如果差值小于0，显然 val 成为最小值，否则最小值不变
            min = Math.min((long)val,min);
        }
    }

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

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

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

0 赞同 0 条回复

晨普通 2022年10月29日下午10:41

维护一个实际元素与最小值的差值的栈

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        # diffstack作为存储实际元素与最小元素差值的栈
        self.diffstack = []
        self.minx = 2147483647


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        if not self.diffstack:
            self.minx = x
        self.diffstack.append(x-self.minx)

        # # 如果新入栈元素比min小，则min = x
        if x - self.minx < 0:
            self.minx = x


    def pop(self):
        """
        :rtype: None
        """
        # 如果minstack栈顶元素小于0，则更新min的值
        if self.diffstack[-1] < 0:
            self.minx = self.minx - self.diffstack[-1]
        self.diffstack.pop()




    def top(self):
        """
        :rtype: int
        """
        if self.diffstack[-1] > 0:
           return self.diffstack[-1] + self.minx
        else:
            return self.minx - self.diffstack[-1]


    def min(self):
        """
        :rtype: int
        """
        return self.minx

0 赞同 0 条回复

酥合普通 2022年10月29日下午7:35

class MinStack {
    private Deque<Integer> xStack;
    private int min;

    public MinStack() {
        xStack = new LinkedList<>();
        min = 0;
    }

    public void push(int x) {
        if(xStack.isEmpty()){
            xStack.push(0);
            min = x;
            return;
        }
        xStack.push(x - min);
        min = (x - min)  < 0 ? x : min;
    }
    public void pop() {
        if(xStack.isEmpty()){
            return;
        }
        int top = xStack.peek();
        min = top < 0 ? (min - top) : min;
        xStack.pop();
    }

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

    public int min() {
        return min;
    }
}

时间复杂度空间复杂度都为O(1)

0 赞同 0 条回复

猫猫真可爱普通 2022年10月29日下午5:48

两个栈解决，用辅助栈存放最小值

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

0 赞同 0 条回复

阿白普通 2022年10月29日下午5:05

1、data.top中存放当前x与当前minData的差值
2、弹出时，如果data.top为正，则minData不用改变；如果data.top为负，那么它弹出后，minData需要修正为minData-data。

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

    void push(int x) {
        int compare = x - minData;
        data.push(compare);
        minData = compare < 0 ? x : minData;
    }

    void pop() {
        if (data.top() < 0)
            minData -= data.top();
        data.pop();
    }

    int top() {
        return data.top()+minData;
    }

    int min() {
        return minData;
    }
private:
    int minData;
    std::stack<int> data;//存放的是差值
};

0 赞同 0 条回复

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

自己简单写了一个，让用一个栈实现，但是还是有点冗杂，可以再修改

  //只用一个栈来解决
    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;
    }

0 赞同 0 条回复

Gg 普通 2022年10月28日下午8:35

class MinStack {

    Stack<Integer> stk;
    int min;
    public MinStack() {
        stk = new Stack<>();
    }

    public void push(int val) {
        if(stk.isEmpty()){
            min = val;
            stk.push(0);
        }else{
            int compare = val - min;
            stk.push(compare);
            // 更新最小值
            min = Math.min(val,min);
        }
    }

    public void pop() {
        int curr = stk.peek();
        // 差为负数时，说明该元素比压栈时的时比上一个最小值小。此时的min就为push的值val
        // val - compare = min
        if(curr < 0){
            min = min - curr;
        }
        stk.pop();
    }

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

    public int getMin() {
        return min;
    }
}

0 赞同 0 条回复

刺猬普通 2022年10月28日下午8:06

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

    }

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

    }

    void pop() {
        int top = instack.top();
        if(top < 0){
            minvalue = minvalue - top;
        }
        instack.pop();
    }

    int top() {
        if(instack.top() <= 0)
            return minvalue;
        else
            return minvalue + instack.top();
    }

    int min() {
        return minvalue;
    }
};

时间复杂度空间复杂度都为O(1)

0 赞同 0 条回复

狗蛋儿普通 2022年10月27日下午10:21

o(1)的做法就是只维护一个最小值，而不是之前的一个栈。

维护一个值得时候需要在插入的时候得到当前值与最小值的差，问题就来了。
差值是否会导致越界，还是要结合题目来看

class Solution {

public:
    stack<int> out;
    int mim =0;
    void push(int value) {
        if(out.empty()){
            mim = value;
            out.push(value);
        }else{
            int compare = value -mim;
            out.push(value);
            mim = compare < 0 ? value:mim;
        }

    }
    void pop() {
        out.pop();

    }
    int top() {
        return out.top();
    }
    int min() {
        return  mim;
    }
};

0 赞同 0 条回复

绍熙普通 2022年10月27日下午9:42

public class MinStack3 {
    private Stack<Integer> diff = new Stack<Integer>();
    private int minValue;

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

    public void pop() {
        int top = diff.peek();
        minValue = top < 0 ? (minValue - top) : minValue;
        diff.pop();
    }

    public int top() {
        int top = diff.peek();
        return top > 0 ? top + minValue : minValue;
    }

    public int getMin() {
        return minValue;
    }
}

致命缺点：由于存储差值，无法解决溢出的可能问题

0 赞同 0 条回复

Tolkien 永久会员 2022年10月27日下午7:54

用带min属性的链表模拟栈

/**
 * 用链表来作为栈，头结点作为栈顶。因此添加节点和删除节点在链表头进行，此时push，pop时间复杂度均为O(1)
 * 为节点设置min属性，含义为 该节点作为栈顶时，栈中元素的最小值
 * 因此，求栈顶元素即求最小值，时间复杂度为O(1)
 */
public class MyNode {
    int val;
    int min;
    MyNode next;

    public MyNode(int val, int min, MyNode next) {
        this.val = val;
        this.min = min;
        this.next = next;
    }
}

public class OptimalMinStack {
    MyNode stack;
    public OptimalMinStack() { }

    public void push(int x) {
        // 1. 判断栈为空的情况
        int min = stack == null ? x : Math.min(x, stack.min);
        // 2. 从头结点插入新节点，其min为当前栈中元素的最小值
        stack = new MyNode(x, Math.min(x, min), stack);
    }

    public void pop() {
        // 1. 从头结点删除元素
        stack = stack.next;
    }

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

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

0 赞同 0 条回复

天然普通 2022年10月27日下午6:48

学习新思想，刷好每道题
想用一个值去固定最小值，但没有想出来，看的下面道友的思路想法，使用栈去保存每次的最小值
时间复杂度O(1),空间复杂度O(1)

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.lst = []
        self.Min = 100001


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        if not self.lst or self.Min >= x: 
            self.Min =x
        self.lst.append(self.Min)
        self.lst.append(x)


    def pop(self):
        """
        :rtype: None
        """
        o = self.lst.pop()
        cur_min = self.lst.pop()
        if self.lst and o == cur_min:
            temp = self.lst.pop()
            self.Min = self.lst[-1]
            self.lst.append(temp)

    def top(self):
        """
        :rtype: int
        """
        return self.lst[-1]

    def min(self):
        """
        :rtype: int
        """
        return self.Min


# 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()

0 赞同 0 条回复

庄重普通 2022年10月27日下午4:22

// 思路：
//     用链表来模拟栈，链表的属性增加一个当前最小值
class MinStack {
public:
    /** initialize your data structure here. */
    //节点结构体
    struct ListNode{
        int m_val;
        int m_min;
        ListNode* m_next;
        ListNode(int val, int min, ListNode* next)
                :m_val(val),m_min(min),m_next(next){}
    };
    MinStack() :m_head(NULL){}

    void push(int x) {
        if(m_head == NULL)//第一个节点
            m_head = new ListNode(x ,x ,NULL);
        else
            //进行头插
            m_head = new ListNode(x,::min(x,m_head->m_min),m_head);
    }

    void pop() {
        ListNode* pTmp = m_head;
        m_head = m_head->m_next;
        delete pTmp;
    }

    int top() {
        return m_head->m_val;
    }

    int min() {
        return m_head->m_min;
    }
    ListNode* m_head;
};
//时间复杂度O(1)
//空间复杂度O(n) n为需要的链表长度

0 赞同 0 条回复

黎昕普通 2022年10月27日下午2:04

剑指 Offer 30. 包含min函数的栈的改进题目

题目要求

规定数据范围为[-100000,100000];

使得空间复杂度和时间复杂度都是O(1);

解法思路

核心思想：使栈中的数据不仅能够保有原来数据是什么的信息，同时保有最小值是如何变化的信息。

push

维护一个用于存储差值的栈（差=实际元素-当前的min值），栈空时，将min设置为当前元素并将栈底设置为0；栈非空时，计算差值diff，如果diff<0，则当前入栈元素小于当前的min，入栈diff并更新元素，如果diff>=0，说明无需更新min，直接将diff入栈即可。

pop

如果差值栈栈顶元素<0，说明出栈当前栈顶元素后，min值会变大，【因为当前栈顶元素diff<0，所以之前push这个元素的时候，min设置为等于实际值】，而出栈栈顶元素后，min值会被更新为 min-栈顶的diff值。

如果栈顶元素diff>=0，说明此次出栈并不会影响min的值，【因为diff>=0，之前的压栈方式为：计算出diff直接入栈】，所以反向计算实际值 = diff + min。

min

直接返回min。

top

与pop操作比较类似。

如果差值栈栈顶元素diff<0，说明当前元素实际值为当前的min值。

如果diff>=0,说明当前元素实际值=diff+min。

时间复杂度 O(1)

所有相关函数都不涉及遍历操作。

空间复杂度 O(1)

使用了常量的额外空间

代码

//shopee面试题，题目中要求 空间与时间都是O(1),并且限定了数值范围是[-100000,100000]，所以可以使用以下解法，但是本题中使用本解法会产生符号数溢出
#define MAX_LENGTH 10001
typedef struct {
    int dstack[MAX_LENGTH];//difference stack
    int front;//可以不需要front
    int rear;
    int min;
} MinStack;

/** initialize your data structure here. */

MinStack* minStackCreate() {
    MinStack* obj=(MinStack*)malloc(sizeof(MinStack));
    obj->front=0;
    obj->rear=0;
    obj->min=0;//可以不初始化，但是为了规范
    return obj;
}

void minStackPush(MinStack* obj, int x) {
    if(obj->front==obj->rear){//栈空
        obj->min=x;
        obj->dstack[obj->rear++]=0;
    }else{
        int diff=x-obj->min;
        obj->dstack[obj->rear++]=diff;
        if(diff<0){//说明x<min
            obj->min=x;
        }
    }
}

void minStackPop(MinStack* obj) {
    if(obj->dstack[obj->rear-1]<0){//pop之后min将变大，min就是实际的顶元
        int tmp=obj->min;
        obj->min=obj->min-obj->dstack[--obj->rear];
        return tmp;
    }else{
        obj->rear--;
        return obj->min+obj->dstack[obj->rear];
    }
}

int minStackTop(MinStack* obj) {
    if(obj->dstack[obj->rear-1]<0){
        return obj->min;
    }else{
        return obj->dstack[obj->rear-1]+obj->min;
    }
}

int minStackMin(MinStack* obj) {
    return obj->min;
}

void minStackFree(MinStack* obj) {
    free(obj);
}

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, x);

 * minStackPop(obj);

 * int param_3 = minStackTop(obj);

 * int param_4 = minStackMin(obj);

 * minStackFree(obj);
*/

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月27日上午10:59

/**
时间复杂度0(1)
空间复杂度o(1)
实现思路：
在push时同时保存min的值
 */
class MinStack {
    int min = Integer.MAX_VALUE;
    private Stack<Integer> stack1;
    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new Stack<>();
    }

    public void push(int x) {
        if(x < min || stack1.isEmpty()) min = x;
        stack1.push(min);
        stack1.push(x);
    }

    public void pop() {
        int m = stack1.pop();
        int cur_min = stack1.pop();
        if(!stack1.isEmpty() &&  m == cur_min) {
            int tmp = stack1.pop();
            min = stack1.peek();
            stack1.push(tmp);
        }
    }

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

    public int min() {
        return min;
    }
}

0 赞同 0 条回复

yanshuojune 普通 2022年10月26日下午11:52

解题思路：空间O(n)复杂度的解法使用的是辅助栈保存最小值，本题目中，栈用于保存x和min之间的差值，当差值小于0时，更新最小值min为当前x，实现O（1）的空间复杂度，各操作时间复杂度也为O(1)；

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min = 1e5

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

    def pop(self) -> None:        
        x = self.pop()
        self.min = (self.min - x) if x < 0

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

0 赞同 0 条回复

青木普通 2022年10月26日下午11:26

想了很久，只有一个大概的思路，因为想要常数级的空间复杂度，那么最小值的存储只能利用现有的栈，而帅地给了提示注意数值范围，我觉得可以将int的前2个字节用于记录最小值，后面2个字节来记录本来的值，这样就可以完美实现空间复杂度为O(1)了

0 赞同 2 条回复

shuaidi 永久会员 @ 青木 2022年10月26日下午11:45

哈哈，两个2字节记录不了10万的数值哦，不过也是个不错的思路，我也是给了面试官类似的思路。

登录以回复
青木普通 @ shuaidi 2022年10月26日下午11:56

hh忘记这茬了0.0，实在想不出来更好的了，等一下明天的答案@_@

登录以回复

So 普通 2022年10月26日下午10:38

第五天第三题

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

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

    public int getMin() {
        return min;
    }
}

时间复杂度：O(1)，空间复杂度：O(1)

0 赞同 1 条回复

shuaidi 永久会员 @ So 2022年10月26日下午11:46

要给出空间复杂度和时间复杂度哦。

登录以回复

西西弗斯的石头永久会员 2022年10月26日下午9:59

空间复杂度为O（n），时间复杂度为O（1）.

public class solution{
    // 定义两个栈
    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();
    }
}

0 赞同 0 条回复

T 普通 2022年10月26日下午9:19

学习一波帅地方法, 在纸上模拟一下栈的过程就很清晰了。

public class GetMin {
  private Deque<Integer> stack;
  private int min;
  public GetMin() {
    this.stack = new LinkedList<>();
  }
  // 利用插入值跟最小值作差来保证空间和时间都为O(1)
  public void push(int x) {
    // 插入第一个元素，将最小值赋值为0，存入 x - min = 0。
    if(stack.isEmpty()) {
      stack.push(x);
      min = 0;
    } else {
      int compare = x - min;
      stack.push(compare);
      // 如果差值小于零，说明当前插入值比min还小，更新最小值。
      min = compare < 0 ? x : min;
    }
  }

  public void pop() {
    int top = stack.peek();
    // 相当于存入的逆过程。 存入时：x - min = val
    // 此时val<0，min更新为x，所以如果当前最小值被弹出后
    // 上一个就min = x - val
    min = top < 0 ? (min-top) : min;
    stack.pop();
  }

  public int getMin() {
    return min;
  }
}

0 赞同 1 条回复

shuaidi 永久会员 @ T 2022年10月26日下午11:47

虽然没仔细看你的代码，不过正确的方法也是用数值差的方式做哦

登录以回复

波波_1936 普通 2022年10月26日下午4:39

    class MinStack {

//        执行用时：13 ms, 在所有 Java 提交中击败了65.42%的用户 
//        内存消耗：43.5 MB, 在所有 Java 提交中击败了43.42%的用户
//        通过测试用例：19 / 19
        /**
         * 自定义数据结构，存栈的值和当前状态下栈的最小值（通过入栈的时候比较一下然后记录，）
         * 时间复杂度O(1) 没有额外的遍历操作
         * 空间复杂度O(1) 操作push 的时候使用了一个临时遍历
         */
        private class CStack {
            int min;//当前栈内的最小值
            int value;//入栈的值

            CStack(int value, int min) {
                this.value = value;
                this.min = min;
            }

            public int getCurrentMin() {
                //当前栈内的最小值
                return min;
            }
        }

        private Stack stack;

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

        //O(1)
        void push(int x) {
            if (stack.isEmpty()) {
                stack.push(new CStack(x, x));
            } else {
                CStack currTop = stack.peek();
                if (x < currTop.getCurrentMin()) {
                    //x是最小的
                    stack.push(new CStack(x, x));
                } else {
                    stack.push(new CStack(x, currTop.getCurrentMin()));
                }
            }


        }

        //O(1)
        void pop() {
            if (stack.isEmpty()) {
                return;
            }
            stack.pop();
        }

        int top() {
            if (stack.isEmpty()) {
                return -1;
            }
            return stack.peek().value;
        }

        //O(1)
        int min() {
            if (stack.isEmpty()) {
                return -1;
            }
            return stack.peek().getCurrentMin();
        }

    }

0 赞同 0 条回复

【体验面试】shopee面试：变形的最小栈

共以下 34 个回答

照着打，还是挺难理解的

o(1)的做法就是只维护一个最小值，而不是之前的一个栈。

剑指 Offer 30. 包含min函数的栈的改进题目

题目要求

解法思路

push

pop

min

top

时间复杂度 O(1)

空间复杂度 O(1)

代码

# 回答此问题取消回复

【体验面试】shopee面试：变形的最小栈

共以下 34 个回答

照着打，还是挺难理解的

o(1)的做法就是只维护一个最小值，而不是之前的一个栈。

剑指 Offer 30. 包含min函数的栈 的改进题目

题目要求

解法思路

push

pop

min

top

时间复杂度 O(1)

空间复杂度 O(1)

代码

# 回答此问题 取消回复

剑指 Offer 30. 包含min函数的栈的改进题目

# 回答此问题取消回复