糖香香普通 2023年7月1日下午5:36

  class MinStack {

        List<Integer> list;
        //辅助栈
        List<Integer> minlist;
        int min;

        public MinStack() {
            list = new ArrayList<>();
            minlist = new ArrayList<>();
        }

        public void push(int x) {
            list.add(x);
            if (list.size() == 1) {
                min = x;
            } else  {
                min = min > x ? x:min;
            }
            minlist.add(min);
        }

        public void pop() {
            list.remove(list.size() -1);
            minlist.remove(minlist.size() -1);
            if (minlist.size() >0){
                min = minlist.get(minlist.size() -1);
            }
        }

        public int top() {
            return list.get(list.size() - 1);
        }

        public int min() {
            return minlist.get(minlist.size() - 1);
        }
    }

0 赞同 0 条回复

宁永久会员 2023年3月16日下午4:41

使用两个栈来实现

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) {
        stack.push(x);
        if(minStack.isEmpty() || minStack.peek() >= x){
            minStack.push(x);
        }
    }

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

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

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

0 赞同 0 条回复

lucca 普通 2022年12月31日下午5:46

辅助栈同步维护每一个元素还没被取出的时候，最大值是多少，当元素被取出时，辅助栈也要同步取出

class MinStack {

    int N = 20010;
    int[] minS = new int[N], s = new int[N];
    int topM = -1, top = -1;

    /** initialize your data structure here. */
    public MinStack() {
        minS[++topM] = Integer.MAX_VALUE;
    }

    public void push(int x) {
        s[++top] = x;
        int t = Math.min(x, minS[topM]);
        minS[++topM] = t;
    }

    public void pop() {
        --top;
        --topM;
    }

    public int top() {
        return s[top];
    }

    public int min() {
        return minS[topM];
    }
}

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

hmmm 普通 2022年11月30日下午8:15

class MinStack {
public:
stack<int> x_stack;
stack<int> min_stack;

    /** initialize your data structure here. */
    MinStack() {
        min_stack.push(INT_MAX);
    }

    void push(int x) {
        if(x < min_stack.top())
        {
            min_stack.push(x);
        }
        else 
        min_stack.push(min_stack.top());
        x_stack.push(x);
    }

    void pop() {
        x_stack.pop();
        min_stack.pop();
    }

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

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

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

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:04

class MinStack {
    stack<int> x_stack;
    stack<int> min_stack;
public:
    /** initialize your data structure here. */
    // vector<int> res;
    MinStack() {
        // min_stack.push(INT_MAX);
        min_stack.push(INT_MAX);
    }

<pre><code>void push(int x) {
    x_stack.push(x);
    // minst.push(::min(x,s1.top()));
    min_stack.push(::min(min_stack.top(), x));
    //C++的类的成员函数中要使用C头文件定义的函数需要使用 :: 作用域符号
}

void pop() {
    x_stack.pop();
    min_stack.pop();
}

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

int min() {
    return min_stack.top();
}
</code></pre>

};

// class MinStack {
//     stack<int> x_stack;
//     stack<int> min_stack;
// public:
//     MinStack() {
//         min_stack.push(INT_MAX);
//     }

//     void push(int x) {
//         x_stack.push(x);
//         min_stack.push(::min(min_stack.top(), x));
//     }

//     void pop() {
//         x_stack.pop();
//         min_stack.pop();
//     }

//     int top() {
//         return x_stack.top();
//     }

//     int min() {
//         return min_stack.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 条回复

努力刷题普通 2022年11月30日上午8:11

构造一个辅助栈 只存储小的数
class MinStack(object):

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

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack.append(x)
        if self.min_st:
            self.min_st.append(min(x, self.min_st[-1]))
        else:
            self.min_st.append(x)

    def pop(self):
        """
        :rtype: None
        """
        self.stack.pop(-1)
        self.min_st.pop(-1)


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


    def min(self):
        """
        :rtype: int
        """
        return self.min_st[-1]

0 赞同 0 条回复

PatNick 普通 2022年11月20日下午3:22

import math
class MinStack1:

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


    def push(self, x: int) -> None:
        self.stack.append(x)

    def pop(self) -> None:
        self.stack.pop()

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

    def min(self) -> int:
        # 正无穷大
        min_value = math.inf
        for _ in self.stack:
            min_value = _ if min_value > _ else min_value

        return min_value


class MinStack2:

    def __init__(self):
        self.stack = []
        # 用于存放最小值的栈，每次有push时，min_stack就会push当前索引下的最小值，因此同时也要一起pop
        self.min_stack = [math.inf]

    def push(self, x: int) -> None:
        self.stack.append(x)
        self.min_stack.append(min(minStack[-1],x))

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

    def min(self) -> int:


        return self.min_stack[-1]

0 赞同 0 条回复

如梦似歌普通 2022年11月10日下午8:41

class MinStack {

    //定义两个栈，一个主栈stack用于保存元素，一个辅助栈用于存储与每个元素对应的最小值
    Deque<Integer> stack;
    Deque<Integer> minstack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new LinkedList<Integer>();
        minstack = new LinkedList<Integer>();
    }

    public void push(int x) {
        stack.push(x);
        //当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，并将这个最小值存入到辅助栈中
        if(minstack.isEmpty()){
            minstack.push(stack.peek());
        }else{
        minstack.push(Math.min(minstack.peek(), x));
        }
    }

    public void pop() {
        //当一个元素要出栈时，将主栈顶元素和辅助栈顶元素一起弹出
        stack.pop();
        minstack.pop();
    }

    public int top() {
        //直接在主栈中求出栈顶元素即可
        return stack.peek();
    }

    public int min() {
        //任意时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中
        return minstack.peek();
    }
}

0 赞同 0 条回复

lobort 普通 2022年11月4日下午10:33

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

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


    public void pop() {
        if(!A.empty()){
            if(A.peek().intValue() == B.peek().intValue()){
                B.pop();
            }
            A.pop();
        }
    }
    public int top(){
        return A.peek();
    }

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

很基础

0 赞同 0 条回复

xye 普通 2022年11月3日上午10:03

type MinStack struct {
    mstack []int
    min []int
}


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


func (s *MinStack) Push(x int)  {
    if len(s.min) == 0 {
        s.min = append(s.min, x)
    }else{
        if x < s.min[len(s.min)-1] {
            s.min = append(s.min, x)
        }else{
            s.min = append(s.min, s.min[len(s.min)-1])
        }
    }
    s.mstack = append(s.mstack, x)
}


func (s *MinStack) Pop()  {
    s.min = s.min[:len(s.min)-1]
    s.mstack = s.mstack[:len(s.mstack)-1]
}


func (s *MinStack) Top() int {
    return s.mstack[len(s.mstack)-1]
}


func (s *MinStack) Min() int {
    return s.min[len(s.min)-1]
}

利用两个数组实现栈和min

0 赞同 0 条回复

cute. 普通 2022年11月1日下午9:14

思路：
利用两个栈解决此问题
入栈时normalStack正常入栈，而minStack入栈的元素需要和原先元素进行比较，如果小于当前的栈内元素则将其入栈

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.normalStack = [];
    this.minStack = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.normalStack.push(x);
    if(!this.minStack.length){
        this.minStack.push(x);
    } else {
        let min = this.minStack[this.minStack.length-1];
        if(x<min){
            this.minStack.push(x);
        } else {
            this.minStack.push(min);
        }
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.minStack.pop();
    this.normalStack.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.normalStack[this.normalStack.length-1];
};

/**
 * @return {number}
 */
MinStack.prototype.min = function() {
return this.minStack[this.minStack.length-1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

0 赞同 0 条回复

一只骆驼普通 2022年11月1日下午7:30

用另一个栈把当前栈内的最小元素存储在栈顶

class MinStack {
    Deque<Integer> minStack;
    Deque<Integer> xStack;
    /** initialize your data structure here. */
    public MinStack() {
        minStack = new ArrayDeque<>();
        xStack = new ArrayDeque<>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {

        xStack.push(x);
        minStack.push(Math.min(x,minStack.peek()));
    }

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

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

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

0 赞同 0 条回复

Asphyxia 普通 2022年11月1日下午4:51

辅助栈

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

    }

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

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

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

    int min() {
        return m.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 条回复

王艺超普通 2022年10月31日下午5:01

只需要再准备一个栈存储最小的元素，保持两个栈中的元素同步就行

class Solution {
public:

    stack<int> stack1;
    stack<int> stack2;

    void push(int value) {
        stack1.push(value);
        if(stack2.empty() || stack2.top() > value)
        {
            stack2.push(value);
        }
        else stack2.push(stack2.top());
    }
    void pop() {
        stack1.pop();
        stack2.pop();
    }
    int top() {
        return stack1.top();
    }
    int min() {
        return stack2.top();
    }
};

0 赞同 0 条回复

cxxz 普通 2022年10月31日上午12:23

先用了两个容器，发现时间和空间效果很差。于是看题解。直接存一个pair，每一个push进去的pair都存放了当前的值和截止到目前的最小值。其他正常操作。需要注意的点是pop的时候弹走的是否为最小值的元素

class MinStack {
public:
    /** initialize your data structure here. */
    stack> sk_min;
    MinStack() {
        // first = val  secone = min
        sk_min.push(pair (INT_MAX, INT_MAX));
    }

    void push(int x) {
        int min_num = min(x, sk_min.top().second);
        sk_min.push(pair(x, min_num));
    }

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

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

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

时间O(1)
空间O(n)

0 赞同 0 条回复

马啸天永久会员 2022年10月30日下午8:39

    //全部数据进入stack1
    Stack<Integer> stack1;
    //仅存储比stack2原来数小的元素
    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()) {
            stack2.push(x);
        }
    }

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

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

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

0 赞同 0 条回复

云雾里普通 2022年10月30日上午10:57

class MinStack {
    //push全部数据
    Stack<Integer> stack;
    //为空或者比栈顶小则push
    Stack<Integer> stack2;

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

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

    public void pop() {
        Integer pop = stack.pop();
        if(!stack2.isEmpty()&&stack2.peek().equals(pop)){
            stack2.pop();
        }
    }

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

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

0 赞同 0 条回复

symbol 普通 2022年10月29日下午8:58

type MinStack struct {
    stack []int

}


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


func (this *MinStack) Push(x int)  {
    this.stack = append(this.stack, x)
}


func (this *MinStack) Pop()  {
    this.stack = this.stack[:len(this.stack)-1]
}


func (this *MinStack) Top() int {
    value := this.stack[len(this.stack)-1] //弹出栈顶值
    this.stack = this.stack[:len(this.stack)-1] //更新栈元素
    return value
}


func (this *MinStack) Min() int {
    min_num := this.stack[0]
    //for 循环暴力找出最小值
    for i := 0;i < len(this.stack);i++{
        if min_num < this.stack[i]{
            min_num = this.stack[i]
        }
    }
    return min_num
}

0 赞同 0 条回复

阿白普通 2022年10月29日下午2:31

辅助栈存放每次入栈时的栈中和当前值间的最小值

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        minData.push(INT_MAX);
    }

    void push(int x) {
        data.push(x);
        minData.push(std::min(minData.top(), x));
    }

    void pop() {
        data.pop();
        minData.pop();

    }

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

    int min() {
        return minData.top();
    }
private:
    int minPos;
    std::stack<int> data;
    std::stack<int> minData;
};

0 赞同 0 条回复

Ruby🗽 普通 2022年10月28日下午4:28

class MinStack {

        Stack<Integer> stack1;
        Stack<Integer> 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()){
            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 条回复

潜行1 我是火车王！普通 2022年10月28日下午1:12

使用两个辅助栈
时间 O(1)
空间 O(N)

// Core method:
// The peek of minStack is always minimum elem.
type MinStack struct {
    // Two stacks
    stack []int
    minStack []int
}

func Constructor() MinStack {
    return MinStack{
        stack: []int{},
        // Init: store a MaxInt inside
        minStack: []int{math.MaxInt64},
    }
}

func (this *MinStack) Push(x int)  {
    this.stack = append(this.stack, x)
    top := this.minStack[len(this.minStack)-1]
    this.minStack = append(this.minStack, min(x, top))
}

func (this *MinStack) Pop()  {
    this.stack = this.stack[:len(this.stack)-1]
    this.minStack = this.minStack[:len(this.minStack)-1]
}

func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MinStack) Min() int {
    return this.minStack[len(this.minStack)-1]
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

0 赞同 0 条回复

晨普通 2022年10月28日下午1:04

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        # stack作为存储的栈，minnstack作为得到最小元素的辅助栈
        self.stack = []
        self.minstack = []


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack.append(x)
        # 如果辅助栈栈空或者新加入的元素比栈顶元素小，则x进入辅助栈
        if not self.minstack or self.minstack[-1] >=x:
            self.minstack.append(x)


    def pop(self):
        """
        :rtype: None
        """
        # 如果stack栈顶元素与辅助栈站定元素一致，则stack与辅助栈都出栈
        if self.stack.pop() == self.minstack[-1]:
            self.minstack.pop()

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


    def min(self):
        """
        :rtype: int
        """
        return self.minstack[-1]

0 赞同 0 条回复

酥合普通 2022年10月27日下午11:30

class MinStack {

    private Stack<Integer> data;
    private Stack<Integer> ser;


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

    public void push(int x) {
        data.push(x);
        if(ser.isEmpty()) {
            ser.push(x);
            return;
        }
        ser.push(x > ser.peek() ? ser.peek() : x);
    }

    public void pop() {
        data.pop();
        ser.pop();
    }

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

    public int min() {
        return ser.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 条回复

感到自己好渺小普通 2022年10月27日下午11:03

class MinStack {
    //思路：计算栈中最小的值，首先想到的是对栈中元素进行排序，不过时间复杂度为O(n),不满足题中的min pop push的时间复杂度为O(1)
    //然后可以用一个变量记录栈中的最小值，虽然时间复杂度为O(1),但是栈是动态的，如果最小值被弹出，那么元素中次小的值没有被保存，也不行
    //看了题解，可以用两个栈来实现最小栈，一个为主栈，一个为辅助栈，在主栈中压入元素，这时如果辅助栈中没有元素，也同时压入，如果辅助栈中已经存在元素，让要压入的元素x和辅助栈的栈顶元素min比较，如果x比a小，在辅助栈压入x,反之压入a

    /** initialize your data structure here. */
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MinStack() {  //初始化两个栈，一个为主栈(s1),另一个为辅助栈(s2)
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x) {
        s1.push(x);
        if(s2.isEmpty())   //如果辅助栈为空，直接压入x
        {
            s2.push(x);
        }
        else    //如果有元素，比较其与栈顶元素的大小
        {
            s2.push(Math.min(x,s2.peek()));
        }
    }

    public void pop() {
        s1.pop();
        s2.pop();
    }

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

    public int min() {
        return s2.peek();  //栈顶元素存放当前栈中最小的元素
    }
}

0 赞同 0 条回复

just 普通 2022年10月27日下午8:20

//两个栈
包含min函数的栈
class MinStack {
public:
stack st1,st2;
/** initialize your data structure here. */
MinStack() {

}

void push(int x) {
    st1.push(x);
    if(st2.empty() || x <=st2.top()) st2.push(x);

}

void pop() {
   int x=st1.top();
   st1.pop();
   if(x==st2.top()) st2.pop();
}

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

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

};

0 赞同 0 条回复

鸿渐普通 2022年10月27日下午7:54

class MinStack {

    //只用一个栈来解决
     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 条回复

星河普通 2022年10月27日下午6:28

class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            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();
    }
}
时间O(1)空间O(N)

0 赞同 0 条回复

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

别想太多

肯定需要一个辅助栈来完成任务，一开始想的是辅助栈来进行把已有的数据进行排序，但是这样做代码量太大
直接放弃，只存储最小的，注意两个栈的一致性即可！

class Solution {
public:
    stack<int> out,mim;
    void push(int value) {
        out.push(value);
        if(mim.empty() || value<mim.top()) mim.push(value);
        else mim.push(mim.top());
    }
    void pop() {
        out.pop();
        mim.pop();
    }
    int top() {
        return out.top();
    }
    int min() {
        return  mim.top();
    }
};

0 赞同 0 条回复

Chin 普通 2022年10月27日下午3:46

class MinStack {
    Stack<Integer> stack;
    //  辅助栈 每次发生push的时候，栈顶都存一个最小值。
    Stack<Integer> minStack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
        minStack.push(Integer.MAX_VALUE);
    }

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

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

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

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

时间复杂度O1
空间复杂度On

0 赞同 0 条回复

Haoyun 普通 2022年10月27日下午3:44

用辅助栈，每次往minStack推入元素时比较新元素与栈顶元素的大小

var MinStack = function() {
  this.stack = [];
  this.minStack = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
  this.stack.push(x);
  if(!this.minStack.length) {
      this.minStack.push(x);
  } else {
    const temp = this.minStack[this.minStack.length -1];
    this.minStack.push(Math.min(temp, x));
  }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  this.stack.pop();
  this.minStack.pop()
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
   return this.stack.length ? this.stack[this.stack.length -1] : -1;
};

/**
 * @return {number}
 */
MinStack.prototype.min = function() {
   return this.minStack.length ? this.minStack[this.minStack.length -1] : -1;
};

0 赞同 0 条回复

单个酒窝儿普通 2022年10月27日下午3:40

1、首先定义两个栈，一个作为主栈，一个作为辅助栈，主栈用来存储数据，辅助栈用来存储最小值
2、在入栈操作中，A栈肯定是要入元素的，对于B栈来说，判断一下如果B栈为空或者B的top元素大于要入栈的元素，则元素也入B栈
3、执行出栈操作时，先判断A的栈顶元素和B的栈顶元素是不是同一个，如果是则同时出栈，如果不是则A执行出栈
4、top方法，直接执行A的top就可以
5、min方法，直接执行B的min就可以

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {}
    stack<int> A,B;
    void push(int x) {
        A.push(x);
        if(B.empty() || x <= B.top()){
            B.push(x);
        }
    }

    void pop() {
        if(A.top() == B.top()){
            A.pop();
            B.pop();
        }
        else{
            A.pop();
        }
    }

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

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

0 赞同 0 条回复

小肸永久会员 2022年10月27日下午3:26

思路：需要用到一个辅助栈min，栈min的栈顶为当前栈中的最小值。怎么维护栈min，当入栈第一个元素x时，直接将x也入栈到栈min中，当入栈第二个元素e时，与栈min的栈顶元素，即当前栈中的最小值minVlue，作比较，如果e<minValue，说明栈中的最小值需要更新，直接将e入栈到栈min，这样栈min的栈顶就是元素e。如果e>=minValue，说明栈中的最小值不需要更新，直接将栈min的栈顶元素再入栈一次就行。时间复杂度O(1)，空间复杂度O(N)。

class MinStack {
    private Stack stack;
    private Stack min;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        min = new Stack<>();
    }
    public void push(int x) {
        stack.push(x);
        if (min.isEmpty()) {
            min.push(x);
        } else {
            int minValue = min.peek() > x ? x : min.peek();
            min.push(minValue);
        }
    }
    public void pop() {
        stack.pop();
        min.pop();
    }

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

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

0 赞同 0 条回复

虾仁猪心普通 2022年10月27日下午12:54

思路：
和昨天用栈实现队列的思想很相似，用一个栈(栈1)存储入栈元素，另一个栈作为辅助栈（栈2）。
辅助栈的作用是每次要执行入栈操作时：
+ 如果该元素的值小于或等于辅助栈中的栈顶元素，或者辅助栈中没有元素，那么栈1和栈2同时执行入栈操作。
+ 如果该元素的值大于辅助栈中的栈顶元素，那么只有栈1进行入栈操作。
+ 这样我们就可以保证在辅助栈的栈顶元素是栈中的最小元素。
在执行出栈操作时：
+ 如果栈1的执行出栈操作后返回的值与栈2的栈顶元素的值相同，那么栈2也要执行出栈操作。
+ 否则只有栈1执行出栈操作。

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

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

    public void pop() {
        if(s1.pop().equals(s2.peek())){
            s2.pop();
        }

    }

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

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

0 赞同 0 条回复

追普通 2022年10月27日下午12:49

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

    void push(int x) {
        x_stack.push(x);
        min_stack.push(::min(x, min_stack.top()));
    }

    void pop() {
        x_stack.pop();
        min_stack.pop();
    }

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

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

使用一个辅助栈来存放对应位置栈的最小值，注意在出栈的时候辅助的最小栈也要执行出栈操作

0 赞同 0 条回复

黎昕普通 2022年10月27日上午11:16

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

解法思路

使用一个辅助栈b，主栈a正常压入弹出操作，辅助栈b保持为一个非升序列（即栈上方元素小于等于下方元素）。

时间复杂度 O(1)

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

空间复杂度 O(n)

最差情况是本身压入顺序就是一个非升序列。

leetcode beats

时间：70%

空间：50%

代码


#define MAX_LENGTH 10001
typedef struct {
    int stacka[MAX_LENGTH];
    int stackafront;
    int stackarear;
    int stackb[MAX_LENGTH];
    int stackbfront;
    int stackbrear;
} MinStack;

/** initialize your data structure here. */

MinStack* minStackCreate() {
    MinStack* ms=(MinStack*)malloc(sizeof(MinStack));
    ms->stackafront=0;
    ms->stackbfront=0;
    ms->stackarear=0;
    ms->stackbrear=0;
    return ms;
}

void minStackPush(MinStack* obj, int x) {
    //压入a
    obj->stacka[obj->stackarear++]=x;
    //判断压入b
    if(obj->stackbfront==obj->stackbrear||obj->stackb[obj->stackbrear-1]>=x){//b顶元素大于等于x或者b空
    //要注意这里的判断条件，使用了C语言的判断短路操作，所以判断逻辑或的两个条件不能调换顺序，否则在b栈空时压入栈或访问index为-1的位置造成越界
        obj->stackb[obj->stackbrear++]=x;
    }
}

void minStackPop(MinStack* obj) {
    //出a
    obj->stackarear--;//这里取巧了，因为测试不会出现栈空还出栈
    //判断出b
    if (obj->stacka[obj->stackarear] == obj->stackb[obj->stackbrear - 1]) {//如果b栈顶元素与a出栈元素相同，则出栈b，同样这里略去了对栈空等意外情况的判断
        obj->stackbrear--;
    }
}

int minStackTop(MinStack* obj) {
    return obj->stacka[obj->stackarear-1];
}

int minStackMin(MinStack* obj) {
    return obj->stackb[obj->stackbrear-1];
}

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

class MinStack {

    /** initialize your data structure here. */
    public MinStack() {
      A = new Stack<>();
      B = new Stack<>():

    }

    public void push(int x) {
      A.add(x);
      if(B.isEmpty() || B.peek() >= x){
        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 条回复

绍熙普通 2022年10月27日上午10:35

解题思路：
普通栈的 push() 和 pop() 函数的复杂度为 O(1)O(1) ；而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N)O(N) 。

本题难点：将 min() 函数复杂度降为 O(1)O(1) ，可通过建立辅助栈实现；
数据栈 AA ：栈 AA 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。
辅助栈 BB ：栈 BB 中存储栈 AA 中所有非严格降序的元素，则栈 AA 中的最小元素始终对应栈 BB 的栈顶元素，即 min() 函数只需返回栈 BB 的栈顶元素即可。
因此，只需设法维护好栈 BB 的元素，使其保持非严格降序，即可实现 min() 函数的 O(1)O(1) 复杂度。

class MinStack {

    Stack<Integer> 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() || B.peek() >= x)
            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 条回复

是梦终空永久会员 2022年10月27日上午10:35

辅助栈的思路
时间O(1)
空间O(n)

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

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

    public void pop() {
        if(st1 != null){
            if(st1.peek().intValue() == st2.peek().intValue())
                st2.pop();
        }
        st1.pop();
    }

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

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

0 赞同 0 条回复

刺猬普通 2022年10月27日上午10:33

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

    }

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

    }

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

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

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

空间复杂度取决于入栈数字的大小关系，因为每次是将小于等于当前最小值的数入栈到辅助栈

0 赞同 0 条回复

@ 普通 2022年10月27日上午10:13

思路：用到2个辅助栈，一个存放数据，另一个动态的实时存放最小值。
时间复杂度：O(1)

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


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

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

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

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

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

0 赞同 0 条回复

你有点可爱喔普通 2022年10月27日上午9:48

基本思路：使用两个栈。其中一个栈作为辅助栈，主要找入栈元素中最小的值，在入栈的时候进行对辅助栈进行判断，并且下一个入栈元素是否<=辅助栈中栈顶的元素。出栈时，需要判断辅助栈中top元素值是是否与另一个栈的值相等。
时间复杂度：O(1)
空间复杂度：O(n)

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() || x<=s2.peek()){
             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 条回复

wxc 普通 2022年10月27日上午9:12

啊

class MinStack:

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


    def push(self, x: int) -> None:
        self.s1.append(x)
        self.s2.append(min(x,self.s2[-1]))


    def pop(self) -> None:
        self.s1.pop()
        self.s2.pop()


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


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

0 赞同 0 条回复

cxc 普通 2022年10月27日上午12:23

class MinStack {

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

    public void push(int x) {
        a.push(x);
        if(b.isEmpty() || x <= b.peek()){
            b.push(x);
        }
    }

    public void pop() {
        //这里比较关键，如果a弹出，则需要对b中相同值弹出，保证一致性
        if(a.pop().equals(b.peek())){
            b.pop();
        }
    }

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

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

0 赞同 0 条回复

Error 普通 2022年10月26日下午11:56

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        # 空间换时间  
        self.stack_A ,self.stack_B = [], []


    def push(self, x: int) -> None:
        self.stack_A.append(x)
        if not self.stack_B or self.stack_B[-1] >= x:
            self.stack_B.append(x)

    def pop(self) -> None:
        if not self.stack_A:
            return
        if self.stack_A[-1] == self.stack_B[-1]:
            self.stack_B.pop()
        self.stack_A.pop()


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


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

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月26日下午11:36

用linkedlist用例有问题？？？

//空间换时间
class MinStack {
    private LinkedList<Integer> stack1;
    private LinkedList<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    public void push(int x) {
        stack1.offerLast(x);
        if(stack2.isEmpty() || stack2.peek().intValue() >= x){
            stack2.offerLast(x);//stack2始终保存最小值
        }
    }

    public void pop() {
       if(!stack1.isEmpty()){
           //Integer, 数值 > 127 I
           if(stack1.getLast().intValue() == stack2.getLast().intValue()){
               //当前弹出元素为最小元素
               stack2.removeLast();
           }
           stack1.removeLast();
       }

    }

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

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

/**
 * 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) 辅助栈
class MinStack {
    private Stack<Integer> stack1;
    private 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().intValue() >= x){
            stack2.push(x);//stack2始终保存最小值
        }
    }

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

/**
 * 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)
class MinStack {
    private Node node;
    private class Node{
        int val;
        int min;
        Node next;
        public Node(int val,int min,Node next){
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
    /** initialize your data structure here. */
    public MinStack() {

    }

    public void push(int x) {
        if(node == null){
            node = new Node(x,x,null);
        }else{
            node = new Node(x,Math.min(x,node.min),node);
        }
    }

    public void pop() {
        node = node.next;
    }

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

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

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

0 赞同 0 条回复

浅夏的无奈普通 2022年10月26日下午11:26

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

class MinStack {
    Stack<Integer> a,b;

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

    public void push(int x) {
        a.add(x);
        if(b.empty()|| b.peek()>=x){
            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();
    }
}

第二种：

class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;
    /** initialize your data structure here. */
    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }

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

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

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

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

0 赞同 0 条回复

Gg 普通 2022年10月26日下午11:17

class MinStack {

    /** initialize your data structure here. */
    Stack<Integer> stk;
    Stack<Integer> minStk;

    public MinStack() {
        // 多用一个最小栈，保存当前栈中最小的元素
        stk = new Stack<>();
        minStk = new Stack<>();
    }

    public void push(int x) {
        stk.push(x);
        int curMin = minStk.isEmpty() ? x:minStk.peek();
        minStk.push(Math.min(curMin,x));
    }

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

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

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

0 赞同 0 条回复

派大星普通 2022年10月26日下午11:11

class MinStack {
//用集合来实现栈，调用集合的方法
//时间复杂度O(1)
//空间复杂度O(n)
    /** initialize your data structure here. */
    List<Integer> stack;
    public MinStack() {
    stack = new ArrayList<>();
    }

    public int min(){
        Integer m = Collections.min(stack);
        String s = m.toString();
        int a = Integer.parseInt(s);
        return a;
    }
    public void push(int value){
        stack.add(value);
    }
    public int pop(){
        int a = stack.remove(stack.size()-1);
        return a;
    }
    public int top(){
        int a = stack.get(stack.size()-1);
        return a;
    }
}

0 赞同 0 条回复

Y7n05h 普通 2022年10月26日下午11:05

class MinStack {
public:
    /** initialize your data structure here. */
    struct Node {
        int min;
        int value;
    };
    vector<Node> stack;
    MinStack() {
    }

    void push(int x) {
        if (stack.empty() || x <= stack.back().min) {
            stack.push_back(Node{.min = x, .value = x});
            return;
        }
        stack.push_back(Node{.min = stack.back().min, .value = x});
    }

    void pop() {
        stack.pop_back();
    }

    int top() {
        return stack.back().value;
    }

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

push 同时记录当前最小值

0 赞同 0 条回复

猫猫真可爱普通 2022年10月26日下午10:34

用两个栈进行操作，A栈存正常数据，保证正常的出栈入栈操作，B栈严格存放从大到小的数据，这样min操作就是查看B栈的栈顶元素。注意出栈要判断A栈出栈的元素是否是B栈栈顶元素，避免A、B栈元素不一致。

class MinStack {
    Stack<Integer> A;
    Stack<Integer> B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            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 条回复

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

解题思路：创建主栈和辅助栈，主栈执行正常的push、pop等操作，辅助栈在每次push时，和栈顶最小元素对比，只有小于等于最小元素才入栈，出栈时也是类似操作；
时间复杂度：O(1)
空间复杂度：O(n)

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack1 = []
        self.stack2 = []

    def push(self, x: int) -> None:
        self.stack1.append(x)
        if not self.stack2 or (x <= self.stack2[-1]):
            self.stack2.append(x)

    def pop(self) -> None:        
        if self.stack1[-1] == self.stack2[-1]:
            self.stack2.pop()
        self.stack1.pop()

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

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

0 赞同 0 条回复

天然普通 2022年10月26日下午10:18

一个栈记录，另一个栈进行排序，把最小的放在栈顶

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.lst1,self.lst2 =[],[]


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.lst1.append(x)
        if not self.lst2 or self.lst2[-1] >=x:
            self.lst2.append(x)


    def pop(self):
        """
        :rtype: None
        """

        if self.lst1.pop()==self.lst2[-1]:
            self.lst2.pop()

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


    def min(self):
        """
        :rtype: int
        """
        return self.lst2[-1]

0 赞同 0 条回复

庄重普通 2022年10月26日下午9:54

// 思路；
//     栈1正常push/pop,栈2记录栈1中的最小值
//     如果入栈的值比栈2中的栈顶元素小的话，该元素也入栈2
//     此时，栈2中的元素，从顶至底呈递增关系，栈2顶为最小值
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

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

    void pop() {
        if(sta1.empty()) return;
        if(sta1.top() == sta2.top())
            sta2.pop();
        sta1.pop();
    }

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

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

    stack sta1;
    stack sta2;
};
//时间复杂度O(1)
//空间复杂度O(n)
// 思路：
//     用链表来模拟栈，链表的属性增加一个当前最小值
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 条回复

Tolkien 永久会员 2022年10月26日下午9:44

辅助栈
1. 时间复杂度：O(1)
2. 空间复杂度：O(n)
3. 代码

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


<pre><code>/**
 * initialize your data structure here.
 */
public MinStack() {
    stack = new Stack<>();
    minStack = new Stack<>();
    // 防止空指针
    minStack.push(Integer.MAX_VALUE);
}

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

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

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

public int min() {
    return minStack.peek();
}
</code></pre>

}

0 赞同 0 条回复

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

第五天第一题

class MinStack {
    Stack<Integer> stack1;
    Stack<Integer> 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()) {
            if (stack1.pop().intValue() == stack2.peek().intValue()) {
                stack2.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 条回复

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

栈1正常入栈出栈，栈2的栈顶元素是栈1所有元素的最小值

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().intValue()>=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 赞同 1 条回复

西西弗斯的石头永久会员 @ 西西弗斯的石头 2022年10月26日下午8:50

Integer：-128 — 127 缓存
这里注意Integer如果超过上面那个范围，就会出现值相等，但比较不相等的情况，需要使用intValue()转化为int类型

登录以回复

mpweixin用户永久会员 2022年10月26日下午8:17

class MinStack {
    Stack<Integer> datastack;
    Stack<Integer> minstack;
    public MinStack() {
       datastack=new Stack<>();
       minstack=new Stack<>();
    }
    public void push(int x) {
       if(minstack.isEmpty()||minstack.peek()>x){
           minstack.push(x);
           datastack.push(x);
       }else{
           minstack.push(minstack.peek());
           datastack.push(x);
       }

    }
    public void pop() {
        datastack.pop();
        minstack.pop();
    }
    public int top() {
        return datastack.peek();
    }
    public int min() {
       return minstack.peek();
    }
}

最重要的算法思路：我认为是就是那个1.（最重要）最小栈的栈顶永远都是最小的值
2.往里面push的时候push进来的值和栈顶的值比较一下

0 赞同 0 条回复

Whatever 永久会员 2022年10月26日下午8:05

额外创建栈，保存最小元素，保证该栈栈顶为最小元素即可

class MinStack {

    /** initialize your data structure here. */
    Stack<Integer> stack,minStack;
    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);
        }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 条回复

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

//想要快速获得最小值，可以维护一个最小值栈
// 时间复杂度O(1)
// 空间复杂度O(n)

class MinStack {
    Deque<Integer> stack;
    Deque<Integer> min;

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

    public void push(int x) {
        stack.push(x);
        if(min.isEmpty()){
            min.push(x);
        }
        else{
            int temp = min.peek();
            min.push(Math.min(temp, x));
        }
    }

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

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

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

0 赞同 0 条回复

易水寒永久会员 2022年10月26日下午7:21

stack.peek()返回的是对象！！！这里把我坑惨了

class MinStack {

    Stack<Integer> s1;
    Stack<Integer> s2;

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

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

    public void pop() {

        if(s1.peek().equals( s2.peek())) {
            s2.pop();
        }
        s1.pop();
    }

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

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

0 赞同 0 条回复

乱世枭雄普通 2022年10月26日下午7:05

思路
需要两个栈来操作。栈1存正常数据，栈2传min值
每次进栈时，栈1正常，栈2判断与栈顶元素大小关系
每次出栈时，栈1正常，栈2判断与栈顶元素是否相等
保证栈2顶永远是栈1中的最小值

class MinStack {
    Stack<Integer> stack1;
    Stack<Integer> 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()){
            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 条回复

T 普通 2022年10月26日下午5:31

代码

class MinStack {
    private LinkedList<Integer> minStack, stack;
    /** initialize your data structure here. */
    public MinStack() {
        this.minStack = new LinkedList<>();
        this.stack = new LinkedList<>();
    }
    // minStack作为辅助栈用来记录最小元素，
    // 如果当前插入元素小于等于辅助栈顶元素，则存入。
    public void push(int x) {
        stack.push(x);
        if(minStack.isEmpty() || minStack.peek() >= x) {
            minStack.push(x);
        }
    }

    public void pop() {
        if(stack.pop().equals(minStack.peek()))
            minStack.pop();
    }

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

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

0 赞同 0 条回复

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

//和最后一题代码一致
   //包含min函数的最小栈
    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<CStack> 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 条回复

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

共以下 63 个回答

辅助栈同步维护每一个元素还没被取出的时候，最大值是多少，当元素被取出时，辅助栈也要同步取出

别想太多

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

解法思路

时间复杂度 O(1)

空间复杂度 O(n)

leetcode beats

代码

# 回答此问题取消回复

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

共以下 63 个回答

辅助栈同步维护每一个元素还没被取出的时候，最大值是多少，当元素被取出时，辅助栈也要同步取出

别想太多

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

解法思路

时间复杂度 O(1)

空间复杂度 O(n)

leetcode beats

代码

# 回答此问题 取消回复

# 回答此问题取消回复