【基本数据结构】变形题：最小栈的最优解-跟着帅地玩副业，开拓第二曲线PlayOffer

mpweixin用户普通 2023年7月22日下午1:52

class MinStack {
//对数值有限制，因为存储差值会越界，时间空间复杂度都为O(1)
Stack stack;
Integer min;

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

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

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

}

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

public int min() {
    return min;

}

}

0 赞同 0 条回复

淡色花樱普通 2023年7月17日上午10:44

“`java
public class 设计一个有gitMina的栈{
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 条回复

憨憨永久会员 2023年7月5日下午6:15

通过储存差值来减少空间

public class minStack {
    private Stack<Integer> 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;
    }
}

0 赞同 0 条回复

BOZ 普通 2023年7月5日上午10:34

【思路】由于[-100000, 100000]数值范围可以产生的最大差值可以用32位int表示，将各个数值与min的差值存入栈中。
【时间复杂度】各个操作均为O(1)
【空间复杂度】额外产生的复杂度为O(1)

class minStack {
    stack<int> diffStack;
    int min;
public:
    void push(int val) {
        if (diffStack.empty()) {
            min = val;
            diffStack.push(0);
        } else {
            int diff = val - min;
            if (diff < 0) min = val;
            diffStack.push(diff);
        }
    }
    void pop() {
        int diff = diffStack.top();
        if (diff < 0) { // is the min, need to change min
            min = min - diff;
        }
        diffStack.pop();
    }
    int top() {
        int diff = diffStack.top();
        if (diff < 0) return min;
        else return (min + diff);
    }
    int getMin() {return min;}
};

0 赞同 0 条回复

Sexypig. 普通 2023年7月4日下午1:38

代码：

from math import inf


class MinStack:
    def __init__(self):
        self.stack = []
        self.min_value = inf  # 初始化最小值为正无穷大

    def push(self, x: int) -> None:
        if x <= self.min_value:
            # 将旧的最小值压入栈中，更新最小值为新的元素
            self.stack.append(self.min_value)
            self.min_value = x
        self.stack.append(x)

    def pop(self) -> int:
        e=self.stack.pop()
        if e == self.min_value:
            # 如果弹出的元素是当前最小值，重新寻找栈中的最小值
            self.min_value = self.stack.pop()
        return e
    def getMin(self) -> int:
        return self.min_value

if __name__ == '__main__':
    stack = MinStack()
    stack.push(3)
    stack.push(2)
    stack.push(1)
    stack.push(5)
    stack.push(0)
    stack.push(-1)
    print(stack.getMin())
    print(stack.pop())
    print(stack.getMin()) 
    print(stack.pop())
    print(stack.getMin()) 
    print(stack.pop())
    print(stack.getMin()) 
    print(stack.pop())
    print(stack.getMin()) 
    print(stack.pop())

该代码实现了一个最小栈类。最小栈是一个特殊的栈数据结构，除了支持常规的压入（push）、弹出（pop）操作外，还支持获取栈中的最小值（getMin）操作。
在该类中，使用一个列表（stack）来存储栈中的元素，并使用一个变量（min_value）来记录当前的最小值。在初始化时，将最小值设置为正无穷大。
push方法用于将元素压入栈中。如果新元素小于等于当前的最小值，需要将旧的最小值压入栈中，并更新最小值为新的元素。然后将新元素压入栈中。
pop方法用于弹出栈顶的元素。首先弹出栈顶的元素，并将其存储在变量e中。如果弹出的元素等于当前的最小值，说明最小值已经被弹出，需要重新寻找栈中的最小值。将栈顶的元素再次弹出，并更新最小值为该元素。最后返回变量e。
getMin方法用于获取栈中的最小值，直接返回变量min_value即可。
该实现的时间复杂度为O(1)，空间复杂度为O(n)，其中n为栈中的元素个数。

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月3日下午10:36

时间复杂度O(1) 空间复杂度O(1)
转成long类型才不会超过边界

class MinStack {

    Stack<Long> stack;
    long min;

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

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

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

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

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

0 赞同 0 条回复

大大普通 2023年7月2日下午6:34

class MinStack {
    //时间复杂度O(1) 空间复杂度O(1)
    //入栈的数是 该数-mini
    //差 记录两数关系///
public:
    /** initialize your data structure here. */
    stack<int> s;
    int mini;
    MinStack() {

    }

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

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

    int top() {
     return s.top()<0?mini:mini+s.top();
    }

    int min() {
     return mini;
    }
};

0 赞同 0 条回复

GGBond 普通 2023年7月1日下午3:00

class MinStack {

    //差值法,
    Stack<Long> stack = new Stack<>();
    long min;
    public MinStack() {

    }

    //栈中只保存 数据与最小值的差值
    public void push(int x) {
        if(stack.isEmpty()){
            //这里保存0，差值为0
            stack.push(0l);
            min = x;
        }else{
            long compare = (long)(x - min);
            stack.push(compare);
            //如果compare小于0，则最小值是x
            min = compare < 0 ? x : min;
        }
    }

    //出栈时，更新最小值。
    public void pop() {
        long compare = stack.pop();
        //是否需要更新最小值？compare小于0，说明当前栈顶元素比最小值小
        min = compare < 0l ? (min - compare) : min;
    }

    public int top() {
        //如果差值小于0，说明当前栈顶元素的原始数据是最小值
        long compare = stack.peek();
        if(compare < 0){
            return Math.toIntExact(min);
        }
        //差值大于0，x - min = compare
        return (int)(compare + min);
    }

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

0 赞同 0 条回复

mpweixin用户普通 2023年7月1日下午1:50

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

    }

    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() {
        int top = stack.peek();
        return top < 0 ? min : top + min;
    }

    public int min() {
        return min;
    }
}

时间复杂度和空间复杂度O(1), 增加了top返回栈顶函数

0 赞同 0 条回复

花老爷普通 2023年6月29日下午11:26

复刻帅地的代码

class minStack {
    private int min;
    private Deque<Integer> stack;

    public minStack() {
        stack = new ArrayDeque<>();
    }
    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 compare = stack.pop();
        if (compare < 0) {
            min -= compare;
        }
    }

    public int getMin() {
        return min;
    }
}

0 赞同 0 条回复

CV大神普通 2023年6月29日下午11:18

 public class BetterMinStack {
        private Deque<Integer> mStack;
        private int min;

        public BetterMinStack() {
            mStack = new LinkedList<>();

        }

        public void push(int val) {
            if (mStack.isEmpty()) {
                mStack.push(val);
                min = val;
            } else {
                int compare = val - min;
                min = compare < 0 ? val : min;
                mStack.push(compare);
            }
        }

        public void pop() {
            int compare = mStack.peek();
            //要在这一步恢复上一个min
            //如果push的时候，compare<0,那么 min = val,所以val - compare = 上一个min
            //如果push的时候，compare>0,那么 min = min,min没有变化
            min = compare > 0? (min - compare) :min;
            mStack.pop();
        }

        public int min() {
            return min;

        }
    }

0 赞同 0 条回复

伏月三十普通 2023年6月28日下午9:47

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

public class getMin {
    ArrayDeque<Integer> stack=new ArrayDeque<>();
    int min;
    public void push(Integer data){
        if(stack.isEmpty()){
            min=data;
            stack.push(0);
        }else {
            int compare=data-min;
            stack.push(compare);
            //如果是<0的话需要将min更新  如果是负数 新加入的就小
            min=compare<0?data:min;
        }
    }

    public Integer pop(){
        Integer peek = stack.peek();
        //栈顶元素如果是负数 说明最小值也应该一同出栈（把最小值更新了）
        min=peek<0?(min-peek):min;
        return stack.pop();
    }

    public Integer getMin(){
        return min;
    }
}

0 赞同 0 条回复

～普通 2023年6月26日下午10:19

没有其它想法，看的答案，用差值

0 赞同 0 条回复

Bello~ 普通 2023年6月26日上午10:04

插值法，栈中存放元素与最小值的差值，每次top操作就利用最小值和栈顶值计算原值；push操作，如果push的值与最小值差大于等于零不更新最小值，如果小于零就更新最新的最小值；pop操作，如果栈顶元素小于零，说明弹出元素是比当前最小值小的，需要更新最小值，几圈方法位：最新最小值 = 现在最小值 – 栈顶值
时间复杂度O(1)
空间复杂度O(1)

class MinStack {

    Deque<Long> stack;
    long min;

    /**
        * initialize your data structure here.
        */
    public MinStack() {
        stack = new LinkedList<>();
    }

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

    public void pop() {
        if (stack.peek() < 0) min = min - stack.peek();
        stack.pop();
      // 如果要返回值的话，代码如下：
      // return stack.pop + min;
    }

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

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

0 赞同 0 条回复

屠龙手段普通 2023年6月25日下午8:25

栈记录压栈元素和最小值的差值
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_element = float('inf')

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

    def pop(self) -> None:
        tmp = self.stack.pop()
        self.min_element = self.min_element if tmp >= 0 else self.min_element - tmp

    def top(self) -> int:
        return self.min_element if self.stack[-1] < 0 else self.min_element + self.stack[-1]

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


# 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 条回复

Dsjh 普通 2023年6月25日下午5:30

// 看了csdn帅弟的文章
// top函数没解决
// 要限制数值范围
class MinStack {


<pre><code>int m_min = 0;
stack<int> s;
</code></pre>

public:
    MinStack() {

<pre><code>}

void push(int val) {
    if(s.empty()){
        m_min = val;
        s.push(0);
    }
    else{
        // int 可能会溢出，要限制数值范围
        int temp = val-m_min;
        s.push(temp);
        m_min = temp<0 ? val : m_min;

    }
}

void pop() {
    if(s.top()<0){
        m_min = m_min-s.top();
    }
    s.pop();

}
int getMin() {
    return m_min;
}
</code></pre>

};

0 赞同 0 条回复

Ming 普通 2023年6月25日下午2:58

考虑 [-100000, 100000]无溢出的话如何利用一个stack实现

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

0 赞同 0 条回复

张开怀普通 2023年6月25日上午10:25

class SetGetMin{
public:
     // 初始化数据结构
     SetGetMin(){
     }

     void push(int x){
          if (st.empty()){
               mix = x;
               // 初始化为0
               st.push(0);
          }else{
               // 计算差值
               int compare = x-min;
               st.push(compare);
               // 如果差值小于0，显然 x 成为最小值，否则最小值不变
               min = compare<0 ? x : min;
          }
     }
     void pop(){
           int top = st.top();
           // 如果top<0，显然最小值也一并删除，此时更新最小值
          min = top<0 ? (min-top) : min;
          st.pop();
     }

     int getMin(){
          return min;
     }
private:
     stack<int> st;
     int min;
}

0 赞同 0 条回复

怀瑾永久会员 2023年6月24日下午11:04

C++实现

#include <stack>
using namespace std;

class MinStack {
public:
    MinStack() {

    }

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

    void pop() {
        if (s.top() == minStack.top()) {
            minStack.pop();
        }
        s.pop();
    }

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

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

private:
    stack<int> s;
    stack<int> minStack;
};

0 赞同 0 条回复

彦，，# 普通 2023年6月24日下午10:03

啊。借鉴，将最小和本身都放在同一个栈里面。

class MinStack {
public:
    /** initialize your data structure here. */
    int Min=INT_MAX;
    stack<int> st;
    MinStack() {}
    void push(int x) {
        st.push(Min);
        if(x<Min) Min=x;
        st.push(x);
    }


<pre><code>void pop() {
    st.pop();
    Min=st.top();
    st.pop();
}

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

int min() {
    return Min;
}
};

0 赞同 0 条回复

* 普通 2023年6月24日下午9:25

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

public void push(int x) {
    if(x<=min){
        stack.push(min);
        min=x;
    }
    stack.push(x);
}

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

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

public int min() {
    return min;
}

}

0 赞同 0 条回复

大鑫啊普通 2023年6月24日下午3:19

mark一下，mpwexin用户同学、jhfuture同学的代码，看了下实现应该没问题，感谢提供思路

class MinStack {

        int curMin;
        Stack<Integer> stack;

    /** initialize your data structure here. */
    public MinStack() {
        curMin = Integer.MAX_VALUE;
        stack = new Stack();
    }

    public void push(int x) {

        //出现更小值,先保存上一个最小值
        if(x <= curMin){
            stack.push(curMin);  
            curMin = x; //再更新当前最小值为x
        }

        stack.push(x);
    }

    public void pop() {
        int top = stack.pop();

        if(top == curMin){ 
            //下个以元素是之前的最小值，取出来
            curMin = stack.pop();
        }
    }

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

    public int min() { 
        return curMin;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年6月24日下午1:55

时间O(1),空间O(1)没有额外的空间
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() :_ptr(new int[5]),_top(-1),_size(5){}
    ~MinStack()
    {
        delete[] _ptr;
        _ptr = nullptr;
    }
    void push(int x) {
        if(full())
            expand();
        ++_top;
        if(_top==0)
        {
            _min = x;
            _ptr[_top] = 0;
        }
        else
        {
            int compare = x - _min;
            _ptr[_top] = compare;
            _min = compare<0? x:_min;
        }


    }

    void pop() {
        if(_top>=0)
        {
            _min = _ptr[_top]<0?(_min - _ptr[_top]):_min;
            --_top;
        }
    }

    int top() {
        return _ptr[_top]<0?_min:_ptr[_top]+_min;
    }

    int min() {
        return _min;
    }
    bool full()
    {
        return (_top-1)==_size;
    }   
    bool empty()
    {
        return _top==-1;
    }
private:
int* _ptr;
int  _top;
int  _size;
int  _min;
void expand()
{
    int *tmp = new int[_size*2];
    for(int i = 0;i<_size;++i)
    {
        tmp[i] = _ptr[i];
    }
    delete[] _ptr;
    _ptr = tmp;
    _size*=2;
}

};

1 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月24日下午12:25

# 用int记录最小值
class MinStack:

    def __init__(self):
        self.stack = []
        self.minStack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.minStack or val <= self.minStack[-1]:
            self.minStack.append(val)

    def pop(self) -> None:
        if self.stack[-1] == self.minStack[-1]:
            self.minStack.pop()
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minStack[-1]


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

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月24日上午12:27

//看了一下jhfuture同学的思路，写出来了，感谢同学
//思路：如果有最小值来了，先用当前栈保存起来上一个最小值；当最小值走了，多弹一次栈，把上一个最小值拿出来。
class MinStack {

        int curMin;
        Stack<Integer> stack;

    /** initialize your data structure here. */
    public MinStack() {
        curMin = Integer.MAX_VALUE;
        stack = new Stack();
    }

    public void push(int x) {

        //出现更小值,先保存上一个最小值
        if(x <= curMin){
            stack.push(curMin);  
            curMin = x; //再更新当前最小值为x
        }

        stack.push(x);
    }

    public void pop() {
        int top = stack.pop();

        if(top == curMin){ 
            //下个以元素是之前的最小值，取出来
            curMin = stack.pop();
        }
    }

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

    public int min() { 
        return curMin;
    }
}

0 赞同 0 条回复

江畅普通 2023年6月23日下午11:19

国际站看到的一个解答

// 最小栈
// 时间复杂度 O(1)
// 空间复杂度 O(1)
class MinStack {
private:
    // 栈节点定义
    struct StackNode {
        int        val_;    // 栈节点存储的值
        int        minVal_; // 栈当前的最小值
        StackNode* next_;   // 栈的下一元素，链表将栈链起来，从栈顶到栈底
    };

    StackNode* stackTopNode; // 栈顶节点

public:
    MinStack() : stackTopNode(nullptr) {}

    void push(int val) {
        StackNode* node = new StackNode;
        node->minVal_ = val;
        node->val_ = val;
        node->next_ = nullptr;

        if (stackTopNode == nullptr) {
            stackTopNode = node;
        }

        else {
            node->minVal_ = min(node->val_, stackTopNode->minVal_);
            node->next_ = stackTopNode;
            stackTopNode = node;
        }
    }

    void pop() { stackTopNode = stackTopNode->next_; }

    int top() { return stackTopNode->val_; }

    int getMin() { return stackTopNode->minVal_; }
};

0 赞同 0 条回复

yxy 普通 2023年6月23日下午8:12

这个好难

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> st;
    int min_v = 0;
    MinStack() {

    }

    void push(int x) {
        if(st.empty())
        {
            st.push(x);
            min_v=x;
        }
        else
        {
            if(x<=min_v)
            {
                st.push(min_v);
                min_v=x;
            }
            st.push(x);
        }
    }

    void pop() {
        int val = st.top();
        st.pop();
        if(st.size()&&min_v==val)
        {
            min_v = st.top();
            st.pop();
        }
    }

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

    int min() {
        return min_v;
    }
};

/**
 * 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 条回复

Vow the vow。普通 2023年6月23日下午6:53

不用辅助栈的做法。

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(min,x);
        stack.push(x);
    }

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

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

    public int min() {
        return min;
    }

想不到空间复杂度为O(1)的做法

0 赞同 0 条回复

jhfuture 普通 2023年6月23日下午3:27

这道题其实难点在于“怎么保存上一个最小值”，如果只是用一个mini数值进行保存的话，那当min值弹出后就无法知道下一个最小值是什么。然后我们这里可以这样子，更新最小值的时候，将上一个最小值压入栈中，同时出栈时，如果出栈的是最小值，则下一个即为上一个最小值，也将它出栈即可。

class mystack{

    Stack<Integer> stackA;
    int min;
    public mystack(){
        stackA=new Stack();

    }
    public void push(int value){
        if (stackA.isEmpty()){
            min=value;
            stackA.push(value);
        }
        if (!stackA.isEmpty()){
            //如果小于则先把上一个min入栈，同时修改min，再把值入栈。
            if (value<=min){
                stackA.push(min);
                min=value;
                stackA.push(value);
            }else{
                stackA.push(value);
            }
        }

    }
    public int pop(){
        //如果出栈的为最小值，则将最小值出栈，同时将min改为下一个出栈的值(上一个最小)，同时将上一个最小出栈
        Integer result;
        if (stackA.peek().intValue()==min){
           result=stackA.pop();
            min= stackA.pop();
        }else {
            result=stackA.pop();
        }
        return result;
    }
    public int top(){
        return stackA.peek();
    }
    public boolean isEmpty(){
        return stackA.isEmpty();
    }
}

时间复杂度为n，空间复杂度为1.

0 赞同 0 条回复

Yodl. 普通 2023年6月23日下午3:11

方法一：使用一个栈，栈中每次存放当前值和加入值前的最小值；在pop时，直接得到去掉该值后的最小值

class MinStack {
public:
    /** initialize your data structure here. */
    int Min=INT_MAX;
    stack<int> st;
    MinStack() {

    }
    void push(int x) {
        st.push(Min);//加入上一个最小值
        if(x<Min) Min=x;//更新最小值
        st.push(x);//加入该数值
    }

    void pop() {
        st.pop();//pop掉该数值
        Min=st.top();//得到去掉该值后的最小值
        st.pop();//将该最小值也pop掉
    }

    int top() {
        return st.top();//返回栈顶即可
    }

    int min() {
        return Min;
    }
};
//方法二 ：stack 栈中，不能存放原始数值，而是应该存放 差值，啥差值？就是存放栈顶与最小值的差值。

1 赞同 0 条回复

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

共以下 30 个回答

# 回答此问题取消回复

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

共以下 30 个回答

# 回答此问题 取消回复

# 回答此问题取消回复