九号球普通 2023年11月8日下午7:49

“`java
精髓就是用另一个栈存放最小值
class MinStack {
Stack stackA;
Stack stackB;

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

public void push(int x) {
    stackA.push(x);
    if (stackB.isEmpty()) {
        stackB.push(x);
    } else {
        if (x <= stackB.peek()) {
            stackB.push(x);
        }
    }
}

public void pop() {
    Integer val = stackA.pop();
    if (val.equals(stackB.peek())) {
        stackB.pop();
    }
}

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

public int getMin() {
    return stackB.peek();
}

}

0 赞同 0 条回复

招舟子普通 2023年8月25日上午9:52

“`java
class MinStack {
Stack stack1;
Stack stack2;
/** initialize your data structure here. */
public MinStack() {
stack1 = new Stack();
stack2 = new Stack();

}

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

public void pop() {
    if(!stack1.isEmpty()){
    if(stack1.peek().intValue()==stack2.peek().intValue()){
        stack2.pop();
    }
    stack1.pop();
    }
}

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

public int min() {
    return stack2.peek();
}

}

/**
* 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();
*/
注意判空条件和intvalue

0 赞同 0 条回复

mpweixin用户普通 2023年7月21日下午11:00

时间 O(1)
空间 O(n)
class MinStack {

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

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

}

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

}

public void pop() {
    if(!stack1.isEmpty()){
        //Integer 
        if(stack1.peek().intValue() == stack2.peek().intValue()){
        stack2.pop();
        }
        stack1.pop();
    } 

}



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


}

public int min() {
    return stack2.peek();

}

}

0 赞同 0 条回复

橙子陈普通 2023年7月16日上午1:58

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

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

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

    public void pop() {
        if (!stack1.isEmpty()){
            if (stack1.peek().intValue() == stack2.peek().intValue()){
                stack2.pop();
            }
            stack1.pop();
        }
    }

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

    public int min() {
        return stack2.peek();
    }
}

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

0 赞同 0 条回复

淡色花樱普通 2023年7月14日下午4:51

“`java
class MinStack {
private Stack stack;
private Integer min = Integer.MAX_VALUE;
public MinStack() {
stack = new Stack <> ();
}
每次进栈，除了将需要入栈的值放入栈中外，还会把前一最小值入栈
public void push(int x )
还未入栈前的最小值入栈
stack.push(min);
min = x < min ? x : min ; 正常进栈 stack.push(x); } 每次出栈，需要出栈两个，一个是当前栈的最小值，一个是需要出栈的正常值 public void pop(){ stack.pop(); min = stack.pop(); } public int pop(){ return stack.peek(); } public int min() { return min; }

0 赞同 0 条回复

Tang 普通 2023年7月4日下午10:45

class MinStack {

    private Stack<Integer> stack;
    private Integer min = Integer.MAX_VALUE;

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

    /**
    每次进栈，除了将需要入栈的值放入栈中外，还会把前一最小值入栈
     */
    public void push(int x) {
        // 还未入栈前的最小值入栈
        stack.push(min);
        // 获取栈的最小值
        min = x < 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;
    }
}

/**
 * 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();
 */

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

0 赞同 0 条回复

憨憨永久会员 2023年7月4日下午5:47

通过一个辅助栈来维护最小值

class MinStack {

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

    public void push(int x) {
         stack.push(x);
        if(min.isEmpty()||min.peek()>=x){
            min.push(x);
        }
    }

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

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

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

0 赞同 0 条回复

BOZ 普通 2023年7月4日下午4:48

【思路】这个题的思路非常有意思，用两个栈进行实现，一个为正常栈，另一个保存了在栈各个阶段的最小值
【时间复杂度】pop/push/min的复杂度均为O(1)

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

    void push(int x) {
        data.push(x);
        if (min_stack.empty() || min_stack.top() >= x) 
            min_stack.push(x);
    }

    void pop() {
        int val = data.top();
        data.pop();
        if (min_stack.top() == val)
            min_stack.pop();
    }

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

    int min() {
        return min_stack.top();
    }
};

0 赞同 0 条回复

3_🔥 永久会员 2023年7月4日下午2:52

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

    public void push(int x) {
        stack1.push(x);
        if(stack2.isEmpty()||stack2.peek()>=x){
            stack2.push(x);
        }
    }

    public void pop() {
        if(!stack1.isEmpty()){
            if(stack1.peek().intValue() ==stack2.peek().intValue())
                stack2.pop();
            stack1.pop();
        }
    }

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

    public int min() {
        return stack2.peek();
    }
}

采用的和讲解一样的代码

0 赞同 0 条回复

Sexypig. 普通 2023年7月4日上午12:41

代码：

"""
该代码实现了一个最小栈的数据结构。它具有以下方法：
-  `__init__` ：初始化数据结构。
-  `push` ：将元素x推入栈中，并在最小栈中维护当前最小值。
-  `pop` ：从栈中弹出元素，并在最小栈中更新最小值。
-  `top` ：返回栈顶元素。
-  `min` ：返回最小栈中的最小值。
该数据结构使用两个栈来实现。一个栈用于存储元素，另一个栈用于存储当前最小值。每当元素被推入栈中时，如果最小栈为空或者新元素小于等于最小栈的栈顶元素，则将新元素也推入最小栈中。每当元素被弹出栈时，如果弹出的元素等于最小栈的栈顶元素，则同时从最小栈中弹出栈顶元素。
这样，无论何时需要获取最小值，只需访问最小栈的栈顶元素即可。该数据结构的时间复杂度为O(1)。
"""


class MinStack:
    def __init__(self):
        self.stack=[]  # 用于存储栈中的元素
        self.min_stack=[]  # 用于存储当前栈中的最小元素

    def push(self, x: int) -> None:
        self.stack.append(x)  # 将元素 x 入栈
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)  # 如果当前元素 x 是最小元素，则将其入最小栈

    def pop(self)->None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()  # 如果出栈的元素是最小元素，则将最小栈中的对应元素也出栈

    def top(self)->int:
        return self.stack[-1]  # 返回栈顶元素

    def min(self)->int:
        return self.min_stack[-1]  # 返回当前栈中的最小元素


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

该代码实现了一个最小栈的数据结构。它使用两个栈来实现，一个栈用于存储元素，另一个栈用于存储当前栈中的最小元素。具体实现如下：
– __init__ ：初始化数据结构，创建一个空的元素栈和最小栈。
– push ：将元素x推入元素栈中，并在最小栈中维护当前最小值。如果最小栈为空或者新元素小于等于最小栈的栈顶元素，则将新元素也推入最小栈中。
– pop ：从元素栈中弹出元素，并在最小栈中更新最小值。如果弹出的元素等于最小栈的栈顶元素，则同时从最小栈中弹出栈顶元素。
– top ：返回元素栈的栈顶元素。
– min ：返回最小栈中的最小值。
这样，无论何时需要获取最小值，只需访问最小栈的栈顶元素即可。该数据结构的时间复杂度为O(1)。

0 赞同 0 条回复

大大普通 2023年7月1日下午5:16

时间复杂度O（1）
空间复杂度O（n)


//刚开始用的数组，但是数组取最小值发现时间复杂度是O(n)pass

//用辅助栈
class MinStack {
public:

     stack s1;
     stack s2;
    /** initialize your data structure here. */
    MinStack() {
    }
    
    void push(int x) {
     s1.push(x);
     if(s2.empty())
         s2.push(x);
     else {
         if(x<=s2.top())//<=
         s2.push(x);
     }
    }
    
    void pop() {
        if(s1.top()==s2.top()){
         s1.pop();
         s2.pop();
        }
        else s1.pop();
    }
    
    int top() {
       return s1.top();
    }
    
    int min() {
   return s2.top();
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月1日上午11:02

java
class MinStack {
    private Stack<Integer> S;    //用来存放输入值
    private Stack<Integer> minS; //用来存放min值
    /** initialize your data structure here. */
    public MinStack() {
        S = new Stack<>();
        minS = new Stack<>();
    }

    public void push(int x) {
        S.push(x);
        if(minS.isEmpty() || x <= minS.peek()) {
            minS.push(x);
        }
        return;
    }

    public void pop() {
        if(!S.isEmpty()) {
            if(S.pop().intValue() == minS.peek().intValue()) { 
                //注意Integer的自动装箱机制，对于-128~127的数不用创建对象，==对引用类型判断地址相等
                minS.pop();
            }
        }
    }

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

    public int min() {
        return minS.peek();
    }
}

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

0 赞同 0 条回复

GGBond 普通 2023年7月1日上午10:33

class MinStack {
    //辅助栈
    Stack<Integer> stack;
    Stack<Integer> minStack;

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

    //优化
    public void push(int val) {
        stack.push(val);
        minStack.push(Math.min(minStack.peek(),val));
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

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

    public int getMin() {
        return minStack.peek();
    }
}

//不使用额外的空间
class MinStack {
    //栈中不仅仅保存数据，还保存最小元素值
    Stack<Integer> stack;
    //保存当前栈中最小元素
    int min;

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

    //如果入栈元素比min更小，则min先入栈，入栈元素再入栈
    public void push(int val) {
        if(val <= min){
            stack.push(min);
            min = val;
        }
        stack.push(val);
    }

    //如果出栈元素是min，则下一个出栈元素是min
    public void pop() {
        int top = stack.pop();
        if(top == min){
            min = stack.pop();
        }
    }

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

    public int getMin() {
        return min;
    }
}

0 赞同 0 条回复

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

 public class MinStack {
        private Deque<Integer> mStack;
        //辅助栈，记录当前栈的最小值
        private Deque<Integer> minStack;

        public MinStack() {
            mStack = new LinkedList<>();
            minStack = new LinkedList<>();
            minStack.push(Integer.MAX_VALUE);
        }

        public void push(int val) {
            mStack.push(val);
            minStack.push(Math.min(val,minStack.peek()));
        }

        public void pop() {
            mStack.pop();
            minStack.pop();

        }

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

        public int min() {
            return minStack.peek();

        }
    }

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

0 赞同 0 条回复

名字什么的好麻烦普通 2023年6月28日上午11:38

辅助栈

class MinStack {
    Deque<Integer> stack1,stack2;

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

    public void push(int x) {
        stack1.push(x);
        if(stack2.isEmpty()||stack2.peek()>=x)
            stack2.push(x);
    }

    public void pop() {
        if(stack1.pop().equals(stack2.peek()))
            stack2.pop();
    }

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

    public int min() {
        return stack2.peek();
    }
}

0 赞同 0 条回复

地平线真勇敢普通 2023年6月27日下午7:31

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

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

    publlic void push(int x){
        stack1.push(x);
        if(stack2.isEmpty() || x <= stack2.peek().intValue()){
            stack2.push(x);
        }
    }
    public void pop(){
        if(!stack.isEmpty()){
            //
            if(stack1.peek().intValue() == stack2.peek().intValue()){
                stack2.pop();
            }
            stack1.pop();
        }
    }

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

时间复杂度o(1),空间复杂度o(n)

0 赞同 0 条回复

～普通 2023年6月26日下午9:14

class MinStack {
stack datastack;
stack minstack;
public:
/** initialize your data structure here. */
MinStack() {

}

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

void pop() {
    if(datastack.top()==minstack.top()){
        minstack.pop();
    }
    datastack.pop();
}

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

int min() {
    return minstack.top();
}

};
时间复杂度O(1),空间复杂度O(N）

0 赞同 0 条回复

伏月三十普通 2023年6月26日下午8:25

/**
值>127的时候，返回的就是对象，要拿到数值要加 .intValue()
时间复杂度是O(1) 在栈顶直接拿的 时间复杂度就是1
空间复杂度是O(n)
 */

class MinStack {

    /** initialize your data structure here. */
    Deque stack1;
    Deque stack2;
    public MinStack() {
        stack1=new ArrayDeque<>();
        stack2=new ArrayDeque<>();
    }

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

    public void pop() {
        if(stack1.peek().intValue()==stack2.peek().intValue()){
            stack2.pop();
        }
        stack1.pop();
    }

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

    public int min() {
        return stack2.peek();
    }
}

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

张君雅小妹妹普通 2023年6月25日下午9:03

时间复杂度：O(1)
额外空间复杂度：O(n)

class MinStack {
    Stack<Integer> minStack;
    Stack<Integer> stack;

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

    // 使用辅助栈，每压入一个数，同步压入当前最小值
    public void push(int x) {
        stack.push(x);
        if(minStack.isEmpty()){
            minStack.push(x);
        } else {
            minStack.push(Math.min(x, minStack.peek()));
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

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

    public int min() {
        return minStack.peek();
    }
}

0 赞同 0 条回复

残月冷骄阳普通 2023年6月25日下午7:15

Problem: 剑指 Offer 30. 包含min函数的栈

[TOC]

思路

使用另外一个辅助栈记录最小值。

解题方法

在入主栈的时候，判断辅助栈中的最小值是否小于当前push的，如果不小于，则将本次的值加入辅助栈。

复杂度

时间复杂度: $O(1)$
空间复杂度: $O(n)$

最坏情况下，加入n个元素用2n的空间。

Code

class MinStack {

    Stack<Integer> stack;
    Stack<Integer> minStack;

    /** initialize your data structure here. */
    public MinStack() {
        this.stack = new Stack();
        this.minStack = new Stack();

    }

    public void push(int x) {
        if(minStack.isEmpty()|| minStack.peek().intValue() >= x){
            minStack.add(x);
        }
        stack.add(x);

    }

    public void pop() {
        if(!minStack.isEmpty()){
            if(stack.peek().intValue() == minStack.peek().intValue()){
                minStack.pop();
            }
        }
        stack.pop();
    }

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

    }

    public int min() {
        //不判空会抛异常
        return minStack.peek();
    }
}

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

Bello~ 普通 2023年6月25日下午7:06

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

class MinStack {

    Stack<Integer> stack;
    Stack<Integer> minStack;

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

    public void push(int x) {
        stack.push(x);
        if (minStack.empty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        int temp = stack.pop();
        if (minStack.peek() == temp) {
            minStack.pop();
        }
    }

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

    public int min() {
        return minStack.peek();
    }
}

0 赞同 0 条回复

Dsjh 普通 2023年6月25日下午4:23

“`cpp
//c++实现
class MinStack {
public:
/** initialize your data structure here. */
stack s1;
stack s2;
MinStack() {

}

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

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

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

int min() {
    return s2.top();
}

};

0 赞同 0 条回复

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

class MinStack {

    /** initialize your data structure here. */
    Stack<Integer> leftStack;
    Stack<Integer> rightStack;

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

    public void push(int x) {
        leftStack.add(x);
        if(rightStack.empty() || rightStack.peek() >= x)
            rightStack.add(x);
    }

    public void pop() {
        if(leftStack.pop().equals(rightStack.peek()))
            rightStack.pop();
    }

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

    public int min() {
        return rightStack.peek();
    }
}

通过建立辅助栈实现

0 赞同 0 条回复

mpweixin用户普通 2023年6月25日下午12:24

C++实现利用辅助栈每插入一个元素存储当前状态下的最小值在辅助栈中

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s;
    stack<int> minS;

    MinStack() {
        minS.push(INT_MAX);
    }

    void push(int x) {
        s.push(x);
        minS.push(::min(minS.top(), x));//很关键
    }

    void pop() {
        s.pop();
        minS.pop();
    }

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

    int min() {
        return minS.top();
    }
};

0 赞同 0 条回复

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

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:12

这个加个放最小数据的栈

class MinStack {
private: 
    stack<int > minStark;
    stack<int > mainStark;
public:
    /** initialize your data structure here. */
    MinStack() { }
    void push(int x) {
        mainStark.push(x);
        int minVal = x;
        if(!minStark.empty()){
            minVal = (minStark.top() < x)?minStark.top() : x;
        }
        minStark.push(minVal);
    }
    void pop() {
        mainStark.pop();
        minStark.pop();
    }
    int top() {
        return mainStark.top();
    }
    int min() {
        return minStark.top();
    }
};

0 赞同 0 条回复

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

”’java 实现
class MinStack {
Stack A,B;
/** initialize your data structure here. */
public MinStack() {
A=new Stack<>();
B=new Stack<>();
}

public void push(int x) {
    A.add(x);
    if(B.empty()||x<=B.peek()){
        B.add(x);
    }
}

public void pop() {
    if(A.pop().equals(B.peek())){
        B.pop();
    }
}

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

public int min() {
    return B.peek();
}

}

0 赞同 0 条回复

Jerry 普通 2023年6月24日下午9:13

class MinStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public void push(int x) {
        stack.push(x);
        // 维护minStack里的最小元素
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        // 弹出的时候，也要维护minStack
        if (stack.peek().equals(minStack.peek)) {
            minStack.pop();
        }
        stack.pop();
    }

    public int top() {
        return stack.peek(); //top 不需维护minStack
    }

    public int min() {
        return minStack.peek(); //直接返回minStack的栈顶元素即可
    }
}

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

0 赞同 0 条回复

花老爷普通 2023年6月24日下午6:05

辅助栈
时间：O(1)
空间：O(n)

class MinStack {
    private Deque<Integer> stack, minStack;

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

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x < minStack.peek()) {
            minStack.push(x);
        } else {
            minStack.push(minStack.peek());
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

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

    public int min() {
        return minStack.peek();
    }
}

0 赞同 0 条回复

张开怀普通 2023年6月24日下午4:41

使用辅助栈存储最小元素

class Minstack{
public:
     Minstack(){

     }

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

     void pop(){
          if(!stack1.empty()){
               // 出栈元素是最小的，栈2中元素应一同出栈
               if(stack1.top() == stack2.top()){
                    stack2.pop();
               }
               stack1.pop();
          }
     }

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

     int min(){
          if(!stack2.empty()){
               return stack2.top();
          }
          return 0;
     }
private:
     stack<int> stack1, stack2;
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月24日下午2:32

C++
TC: O(1)
SC: O(n)
定义一个栈，栈的元素包含当前的栈和到目前为止的最小值

class MinStack {
public:
    stack<pair<int, int> >stk;
    MinStack() {


<pre><code>}

void push(int x) {
    if (stk.empty()) {
        stk.push({x,x});
    } else {
        int currMin = std::min(stk.top().second, x);
        stk.push({x, currMin});
    }
}

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

int top() {
    int curr = stk.top().first;
    return curr;
}

int min() {
    int currMin = stk.top().second;
    return currMin;
}
</code></pre>

};

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

断舍离永久会员 2023年6月24日下午2:12

/**
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，
 * 调用 min、push 及 pop 的时间复杂度都是 O(1)
 * */
class MinStack {

    Deque<Integer> stack;

    //关键点，同步更新最小值的栈
    Deque<Integer> minStack;

    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
        //确保当任意数第一次push与最大值比较，完成更新最小值
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        stack.push(x);
        int min = minStack.peek();
        //将本次压入值与最小值栈的栈顶对比
        if(x < min){
            minStack.push(x);
        }else {
            minStack.push(min);
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

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

    public int min() {
        return minStack.peek();
    }
}

0 赞同 0 条回复

大鑫啊普通 2023年6月24日上午11:42

时间复杂度：O(1)
空间复杂度：O(n)
1、辅助栈保存当前最小的数据
2、进栈时，s1入栈，判断s2栈顶元素和s1栈顶，是否s1<=s2，是则s2入栈，否则只有s1入栈
3、出栈时，s1正常出栈，s2中栈顶如果与s1相同，则s2也出栈
4、取最小时，取s2栈顶即可

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

    public void push(int x) {
        s1.push(x);
        if(s2.isEmpty() || s2.peek().intValue() >= x){
            s2.push(x);
        }
    }

    public void pop() {
        if(!s1.isEmpty()){
            if(s1.peek().intValue() == s2.peek().intValue()){
                s2.pop();
            }
            s1.pop();
        }
    }

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

    public int min() {
        return s2.peek();
    }
}

0 赞同 0 条回复

硬核洋葱普通 2023年6月24日上午10:29

class MinStack {
public:
    stack<int> stk;
    stack<int> support_stk;

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

    }

    void push(int x) {
        stk.push(x);
        if(!support_stk.empty() && support_stk.top() < x)
            support_stk.push(support_stk.top());
        else
            support_stk.push(x);
    }

    void pop() {
        stk.pop();
        support_stk.pop();
    }

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

    int min() {
        return support_stk.top();
    }
};

/**
 * 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();
 */

所有操作的时间复杂度都是O(1)，空间复杂度O(n)
我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m
辅助栈中的数是对应位置的结果
也可以不使用辅助栈，保留当前最小值和栈中原数与最小值的差值，并且防止溢出使用long long类型

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月24日上午8:07

class MinStack:

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

    def push(self, val: int) -> None:
        self.stack.append(val)
        # 记得查minStack不为空
        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 条回复

局外人普通 2023年6月24日上午12:37

思路：使用辅助栈，保存min的信息。
入栈时若有更小元素，则辅助栈也压入更小元素；若无，则继续压入栈顶元素；
出栈时，数据栈与辅助栈同时出栈；
取最小值时，直接取辅助栈顶部元素即可

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> st;
    stack<int> min_st;

    MinStack() {
        min_st.push(INT_MAX);
    }

    void push(int x) {
        if(x<min_st.top()){
            min_st.push(x);
        }else{
            min_st.push(min_st.top());
        }
        st.push(x);
    }

    void pop() {
        st.pop();
        min_st.pop();
    }

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

    int min() {
        return min_st.top();
    }
};

0 赞同 0 条回复

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

// 包含 min 函数的栈
// 时间复杂度 O(1)
// 空间复杂度 O(N)
class MinStack {
private:
    stack<int> dataStack;
    stack<int> minValStack;

public:
    /** initialize your data structure here. */
    MinStack() { minValStack.push(INT32_MAX); }

    void push(int x) {
        dataStack.push(x);
        // 关键点，每次入栈，存储当前栈最小值的栈同时入栈当前栈的最小值
        minValStack.push(::min(minValStack.top(), x));
    }

    void pop() {
        dataStack.pop();
        minValStack.pop();
    }

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

    int min() { return minValStack.top(); }
};

0 赞同 0 条回复

行动派小彩笔普通 2023年6月23日下午10:34

// 辅助栈
// 空间复杂度，最坏情况，两个栈都是满的，O(n)
// 时间复杂度 O(1)
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stk1;
    stack<int> stk2;
    MinStack() {
        stk2.push(INT_MAX);
    }

    void push(int x) {
        stk1.push(x);
        stk2.push(std::min(x,stk2.top()));
    }

    void pop() {
        stk1.pop();
        stk2.pop();
    }

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

    int min() {
        return stk2.top();
    }
};
// 自己定义栈对象实现
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        _pstack = new int[5];
        _top = -1;
        _size = 5;
        _min = new int[5];
        _min[0] = INT_MAX;
    }
    ~MinStack()
    {
        delete[] _pstack;
        delete[] _min;
        _pstack = nullptr;
        _min = nullptr;
    }
    void push(int x) {
        if(full())
            expand();
        //if(x<_min) _min = x;

        _top++;
        _pstack[_top]=x;
        if(_top==0)
        {
            _min[_top] = x;
        }
        else
        {
            _min[_top] = _min[_top-1]<x? _min[_top-1]:x;
        }

    }

    void pop() {
        if(empty())
            return;
        --_top;
    }

    int top() {
        return _pstack[_top];
    }

    int min() {
        return _min[_top];
    }
    bool empty(){return _top==-1;}
    bool full(){return _top == _size-1;}
private:
    int* _pstack;
    int _top;
    int* _min;
    int _size;

    void expand()
    {
        int* ptmp = new int[2*_size];
        int* pmin = new int[2*_size];
        for(int i=0;i<_size;++i)
        {
            ptmp[i] = _pstack[i];
            pmin[i] = _min[i];
        }
        delete[] _pstack;
        delete[] _min;
        _pstack = ptmp;
        _min = pmin;
        _size*=2;
    }
};

0 赞同 0 条回复

Ming 普通 2023年6月23日下午9:33

class MinStack {
    //stack2仅存放最小元素
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new Stack();
        stack2 = new Stack();
    }

    public void push(int x) {   
        stack1.push(x);
        if(stack2.isEmpty() || x <= stack2.peek().intValue()) {
            stack2.push(x);//更新最小值
        }
    }

    public void pop() {
        if(!stack1.isEmpty()) {
            if(stack1.peek().intValue() == stack2.peek().intValue()) {
                stack2.pop();//更新最小值
            }
        }
        stack1.pop();
    }

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

    public int min() {
        return stack2.peek();
    }
}

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

mpweixin用户普通 2023年6月23日下午9:21

辅助栈
class MinStack:

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

    def push(self, x: int) -> None:
        if not self.min_stack:
            self.min_stack.append(x)
        else:
            if self.min_stack[-1] >= x:
                self.min_stack.append(x)
        self.stack.append(x)

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

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

    def min(self) -> int:
        return self.min_stack[-1]



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

mpweixin用户永久会员 2023年6月23日下午9:20

//两个栈，一个用于正常push,pop等，另一个专门存储当前最小值，称它为“最小栈”，正常弹压栈的时候维护好“最小栈”
class MinStack {

        Stack<Integer> minStack;
        Stack<Integer> stack;

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

    public void push(int x) {
        stack.push(x);

        if(minStack.isEmpty()){
            minStack.push(x);
        }else{
            if(x <= minStack.peek()){//小于等于当前最小，就进去，成为当前最小
                minStack.push(x);
            }
        }


    }

    public void pop() {
        int top = stack.pop();
        if(top == minStack.peek()){ // 弹出的数，是当前最小值，对应最小栈内的值也要弹出
            minStack.pop();
        }

    }

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

    public int min() { 
        return minStack.peek();
    }
}

0 赞同 0 条回复

désire. 普通 2023年6月23日下午8:31

C++:借助辅助栈，有一个栈存储最小元素
class MinStack {
public:
/** initialize your data structure here. */
stack s1,s2;
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;
}

};

0 赞同 0 条回复

mpweixin用户普通 2023年6月23日下午6:44

思路:
初始化两个栈，一个主栈，一个存储某个值入栈时的栈顶的最小元素。
”’C++
class MinStack {
public:
/** initialize your data structure here. */
stack MyStack;
stack minstack;
MinStack() {

}

void push(int x) {
    MyStack.push(x);
    if(minstack.empty()){
        minstack.push(x);
    }
    else{
        int val = x < minstack.top() ? x : minstack.top();
        minstack.push(val);
    }
}

void pop() {
    MyStack.pop();
    minstack.pop();
}

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

int min() {
    return minstack.top();
}

};
”’

0 赞同 0 条回复

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

使用一个辅助栈，来保存当前栈的最小值。

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

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

    public void pop() {
        stack.pop();
        minStack.pop();
    }

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

    public int min() {
        return minStack.peek();
    }

0 赞同 0 条回复

雨落圆荷普通 2023年6月23日下午4:51

class MinStack {
Stack stack1;
Stack stack2;

/** initialize your data structure here. */
public MinStack() {
    this.stack1 = new Stack();
    this.stack2 = new Stack();
}

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

public void pop() {
    if(!stack1.isEmpty()){
        //Integer, 数值 > 127 I
        if(stack1.peek().intValue() == stack2.peek().intValue()){
            stack2.pop();
        }
        stack1.pop();
    }
}

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

}

public int min() {
    return stack2.peek();
}

}
时间复杂度：O(1)
额外空间复杂度：O(n)

0 赞同 0 条回复

小吕普通 2023年6月23日下午4:28

c++只能使用辅助栈，借助整数不行，亲测
stack minst;
stack st;
MinStack() {
minst.push(INT_MAX);
}

void push(int x) {
    st.push(x);
    minst.push(::min(minst.top(),x));
}

void pop() {
    st.pop();
    minst.pop();
}

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

}

int min() {
    return minst.top();
}

0 赞同 0 条回复

yxy 普通 2023年6月23日下午4:20

时间复杂度：O(1)
额外空间复杂度：O(n)

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

    }

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

    void pop() {
        if(st.top()==minst.top())
            minst.pop();
        st.pop();
    }

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

    int min() {
        return minst.top();
    }
};

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

jhfuture 普通 2023年6月23日下午2:30

java实现

class MinStack {

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

    public void push(int x) {
        stackA.push(x);
        if(stackB.isEmpty()||x<=(stackB.peek().intValue())){
            stackB.push(x);
        }
    }

    public void pop() {


        if(!stackA.isEmpty()){
             // 如果刚好出栈的是最小值，即为栈B中的，则栈B也要出栈。
        if(stackB.peek().intValue()==stackA.peek().intValue()){
            stackB.pop();
        }
        stackA.pop();
        }



    }

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

    public int min() {
        return stackB.peek();
    }
}

跟着帅地的思路自己敲了一遍

0 赞同 0 条回复

Yodl. 普通 2023年6月23日下午2:20

方法一：使用两个栈，一个模拟栈，另一个栈记录各元素插入时模拟栈的最小值

class MinStack {
public:
    /** initialize your data structure here. */
    stack s1,s2;
    int stack_min;
    MinStack() {

    }

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

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

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

    int min() {
        return s2.top();
    }
};

0 赞同 0 条回复

　　　　　　　　普通 2023年6月23日下午1:56

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

    }

    void push(int x) {
        a.push(x);
        if(b.empty())b.push(x);
        else b.push(::min(b.top(),x));
    }

    void pop() {
        a.pop();
        b.pop();
    }

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

    int min() {
        return b.top();
    }
};

【时间O(1),空间O(n)】
一个模拟栈，另一个记录最小值

0 赞同 0 条回复

【基本数据结构】剑指 Offer 30. 包含min函数的栈

共以下 50 个回答

思路

解题方法

复杂度

Code

# 回答此问题取消回复

【基本数据结构】剑指 Offer 30. 包含min函数的栈

共以下 50 个回答

思路

解题方法

复杂度

Code

# 回答此问题 取消回复

# 回答此问题取消回复