喵喵神教🐈 普通 2023年11月1日下午1:08

辅助栈思路

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

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

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

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

    public int getMin() {
        return stack2.peek().intValue();
    }
}

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月12日下午10:56

class MinStack {

    /** initialize your data structure here. */
    private Stack<Integer> s1;
    private Stack<Integer> s2;

    public MinStack() {
        s1 = new Stack<Integer>();
        s2 = new Stack<Integer>();

    }

    public void push(int x) {
        //s1正常入栈
        s1.push(x);
        //s2保存最小值，为空时直接压入，否则入栈的值<=s2栈顶值才压入
        if(s2.isEmpty() || x <= s2.peek().intValue()){
            s2.push(x);
        }
    }

    public void pop() {
        if(!s1.isEmpty()){
            //s1正常出栈，s1和s2栈顶值相等时，s2才出栈
            //s1.peek().equals(s2.peek())
            if(s1.peek().intValue() == s2.peek().intValue()){
                s2.pop();
            }
            s1.pop();
        }

    }

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

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

hi 普通 2023年7月24日下午11:12

push 和pop 操作时，两个栈都需要进行操作

class MinStack {
public:
    stack<int> stk, stk_min; //两个栈处理这个问题
    /** initialize your data structure here. */
    MinStack() {

    }

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

    void pop() {
        if(stk.top() == stk_min.top()) stk_min.pop();
        stk.pop();
    }

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

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

今天没时间刷题普通 2023年7月23日下午3:30

方法1：辅助栈栈顶记录最小值 
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }

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

    void pop() {
        if(valStack.top() == minValStack.top())
        {
            minValStack.pop();
        }
        valStack.pop();
    }

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

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

    stack<int> valStack;
    stack<int> minValStack;
};
方法2：原栈记录最小值 push和pop维护_min成员
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        valStack.push(_min);
        if(x <= _min)
        {
            _min = x;
        }
        valStack.push(x);
    }

    void pop() {
        valStack.pop();
        _min = valStack.top();
        valStack.pop();
    }

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

    int min() {
        return _min;
    }

private:
    stack<int> valStack;
    int _min{INT_MAX};
};

0 赞同 0 条回复

wowo 普通 2023年7月23日上午12:30

使用辅助栈，保存非严格降序的元素，返回最小元素时，即返回辅助栈的栈顶元素。时间复杂度O(1)，空间复杂度O(n)

class MinStack:

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

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


    def pop(self) -> None:
        if self.A.pop() == self.B[-1]:
            self.B.pop()


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


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

0 赞同 0 条回复

新禾普通 2023年7月22日下午5:52

// 时间复杂度均为 O(1) 空间复杂度O(N)
class MinStack {
Stack xStack;
Stack minStack;
/** initialize your data structure here. */
public MinStack() {
xStack = new Stack();
minStack = new Stack();
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 条回复

神经蛙普通 2023年7月16日上午10:51

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

class MinStack {

    LinkedList<Integer> stack;
    LinkedList<Integer> minStack;

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

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

        // 最小栈入栈：为空或当前最小值大于等于x
        if (minStack.isEmpty() || minStack.getLast() >= x) {
            minStack.add(x);
        }
    }

    public void pop() {
        // 出栈时若最小栈栈头相等，出栈
        if(stack.removeLast().equals(minStack.getLast())) {
            minStack.removeLast();
        }

    }

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

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

0 赞同 0 条回复

朱志刚普通 2023年7月15日下午10:02

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

    }

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

    void pop() {
        int temp;
        if(!stack1.empty())
        {
        temp=stack1.top();
        stack1.pop();
        }
        if(stack2.top()==temp)stack2.pop();

    }

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

    }

    int min() {
        return stack2.top();

    }
};

测试通过

0 赞同 0 条回复

周小二普通 2023年7月15日下午1:27

//代码
class MinStack {
    private Stack<Integer> mainStack;
    private Stack<Integer> minStack;

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

    public void push(int x) {
        mainStack.push(x);
        if (minStack.isEmpty()) {
            minStack.push(x);
        } else{
            minStack.push(Math.min(minStack.peek(), x));
        }
    }

    public void pop() {
        if (mainStack.isEmpty()) {
            return;
        }
        mainStack.pop();
        minStack.pop();
    }

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

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

0 赞同 0 条回复

ppopp 普通 2023年7月15日上午12:28

/*
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
*/
class MinStack {
stack x_stack;
stack 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));
}

//出栈操作：栈弹出顶端值，Min栈弹出顶端值（或为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 条回复

mpweixin用户普通 2023年7月14日下午2:39

使用辅助stack

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

  void push(int x) {
    if(stack.empty()){
      stack.push_back(make_pair(x,x));
    }
    else{
      int less;
      less = stack.back().second;
      if(less> x )
        less = x;
      stack.push_back(make_pair(x, less));
    }
  }
  void pop() { int ret = stack.back().first;
    stack.pop_back();

  }

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

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

private:
  vector<pair<int, int>> stack;
};
/**
 * 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年7月14日下午1:05

class MinStack {
private:
    stack<long> stk;
    long min_val;
public:
    /** initialize your data structure here. */
    MinStack() {
        min_val = 0;
    }

    void push(int x) {
        if(stk.empty()) {
            min_val = x;
            stk.push(0);
        } else {
            stk.push(x - min_val);
            if(x - min_val <= 0) min_val = x;
        }
    }

    void pop() {
        long temp = stk.top();
        if(temp <= 0) {
            min_val -= temp;
        }
        stk.pop();
    }

    int top() {
        if(stk.top() >= 0) 
            return stk.top() + min_val;
        else 
            return min_val;
    }

    int min() {
        return min_val;
    }
};

栈中记录当前值与最小值的差值，时间空间均为O(1).

0 赞同 0 条回复

Marshan 普通 2023年7月14日上午11:18

//高空间,低时间
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }

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

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

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

    int min() {
        return stack.top().second;
    }
private:
    stack<pair<int,int>> stack;
};

0 赞同 1 条回复

Marshan 普通 @ Marshan 2023年7月14日上午11:19

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

登录以回复

Mby 普通 2023年7月14日上午10:07

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()){
            //数值>127
            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 条回复

Fighting boy😀 普通 2023年7月13日下午10:34

//C++实现
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {

}

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

void pop() {
    if(!stack1.empty()){
        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 stack1, stack2;
};

0 赞同 0 条回复

片言莫语普通 2023年7月13日下午10:18

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()){   //stack1的栈顶元素小于或者等于stack2的栈顶元素 就入辅助栈
            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 条回复

北辰普通 2023年7月13日上午10:09

class MinStack {

    public static Stack<Integer> s,arr;

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

    public void push(int x) {
        s.push(x);
        arr.push(Math.min(x,arr.peek()));
    }

    public void pop() {
        s.pop();
        arr.pop();
    }

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

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

思路：本题最妙的就是使用一个同样的栈来记录在当前栈的情况下，栈中最小元素是谁，刚开始使用的是单调栈来记录最小值，时间复杂度为O（n）超时

0 赞同 0 条回复

Terence💧 普通 2023年7月12日下午11:40

type MinStack struct {
    stack    []int
    minStack []int
}


/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{
        stack: make([]int, 0),
        minStack: make([]int, 0),
    }
}


func (this *MinStack) Push(x int)  {
    this.stack = append(this.stack, x)
    if len(this.minStack) == 0 ||  x < this.minStack[len(this.minStack) - 1]{
        this.minStack = append(this.minStack, x)
    }else {
        this.minStack = append(this.minStack, this.minStack[len(this.minStack) - 1])
    }
}


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


/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Min();
 */

利用辅助栈存当前位置的最小值

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月12日下午11:04

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()){
            //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年7月12日下午10:18

”’java
class MinStack {
//存储栈中的元素
private Stack stack;
//存储当前栈中的最小元素
private Stack minStack;

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

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

    //更新最小栈
    // 如果最小栈为空或新元素 x 小于等于最小栈的栈顶元素，则将 x 压入最小栈
    if(minStack.isEmpty() || x <= minStack.peek()) {
        minStack.push(x);
    }
}

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

    //如果弹出的元素恰好是最小站的栈顶元素，则需要同时从最小栈中弹出元素
    //peek() 是一个栈操作，它返回最小栈的栈顶元素，而不会将栈中的元素弹出
    if(x == minStack.peek()) {
        minStack.pop();
    }
}

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

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

}
”’

0 赞同 0 条回复

#00456B 普通 2023年7月12日下午8:47

用两个栈来完成功能，第一个栈就是正常存储，第二个栈通过判断栈顶元素和新元素的大小来添加较小的元素

class MinStack {
public:
    stack<int> stk;
    stack<int> minstk;
    MinStack() {
        minstk.push(INT_MAX);
    }

    void push(int val) {
        stk.push(val);
        if(val <= minstk.top()){
            minstk.push(val);
        }
    }

    void pop() {
        int temp = stk.top();
        stk.pop();
        if(minstk.top() == temp){
            minstk.pop();
        }
    }

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

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

0 赞同 2 条回复

#00456B 普通 @ #00456B 2023年7月12日下午9:12

不使用辅助栈的话，用一个int变量来记录最小值，然后stack用来记录元素与当前最小元素的差值。

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

    }

    void push(int x) {
        if(stk_diff.empty()){
            minNum = x;
            stk_diff.push(0);
        }
        else{
            stk_diff.push(x-minNum);
            minNum = std::min(x,minNum);
        }
    }

    void pop() {
        if(stk_diff.top() <= 0){
            minNum -= stk_diff.top();
        }
        stk_diff.pop();
    }

    int top() {
        if(stk_diff.top() >= 0){
            return stk_diff.top() + minNum;
        }
        else{
            return minNum;
        }
    }

    int min() {
        return minNum;
    }
};

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

#00456B 普通 @ #00456B 2023年7月12日下午9:23

在leetcode上的原题需要把int 改为long long，否则会溢出

登录以回复

NullPointerException 普通 2023年7月12日下午5:50

class MinStack {
Stack stack;
Stack minstack;
//普通栈的同时定义一个辅助最小栈
/** initialize your data structure here. */
public MinStack() {
stack =new Stack();
minstack =new Stack();
}

public void push(int x) {
    if(minstack.size()==0)
    {

        minstack.push(x);
    }else
    {
        if(x<minstack.peek())
        {
            minstack.push(x);
        }else
        {
            minstack.push(minstack.peek());
        }
    }
    stack.push(x);
}

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

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

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

}

0 赞同 0 条回复

人生何处不青山普通 2023年7月12日下午5:29

辅助栈做法

class MinStack {
    private stack:number[]
    private minStack:number[]
    constructor() {
        this.stack = [];
        this.minStack = [Infinity];
    }

    push(x: number): void {
        this.stack.push(x);
        this.minStack.push(Math.min(x,this.minStack.slice(-1)[0]));
    }

    pop(): void {
        this.stack.pop();
        this.minStack.pop();
    }

    top(): number {
        return this.stack.slice(-1)[0];
    }

    min(): number {
        return this.minStack.slice(-1)[0];
    }
}

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

momo 普通 2023年7月12日下午3:54

包含min函数的栈

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

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

    public void push(int x) {
        stack.push(x);
        if (!min.isEmpty() && x > min.peek()) {
            min.push(min.peek());
        } else {
            min.push(x);
        }
    }

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

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

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

0 赞同 0 条回复

AD钙奶普通 2023年7月12日下午2:54

两种方法：辅助栈 & 单栈差值存储

辅助栈

一个栈正常存储数据，另一个栈用来维护最小值，存入比较过程中元素较小的一个

class MinStack {
    Deque dataStack,minStack;

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

    public void push(int x) {
        dataStack.addFirst(x);
        if(minStack.isEmpty() || x <= minStack.peekFirst()) {
            minStack.addFirst(x);
        }
    }

    public void pop() {
        if(!dataStack.isEmpty()) {
            if(dataStack.peekFirst().equals(minStack.peekFirst())) {
                minStack.removeFirst();
            }
            dataStack.removeFirst();
        }
    }

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

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

差值存储（单栈）

这种方法比较不好理解。
所谓存差值，就是data = x - min；data就是差值
push：刚开始栈为空，存入最小值；栈不为空，存入差值。
pop：判断栈顶元素是否大于0，再次强调，栈中存的是差值，不是本身。我们通过判断栈顶元素是否大于0可以知道，push进来的那个数是不是当前栈中的最小值，如果大于0，说明 x > min，那存入的就不是最小值，我们直接弹出差值。
如果小于0，说明 x < min，说明压进来的值比当前min值还小，那它应该才是最小值，它依旧是要被弹出的，此时min = 当前这个值。但在此之前，你需要更新这个最小值。为什么？因为它是当前栈的最小值，弹出之后，谁会拿到这个最小的称号？这个问题需要考虑。简单运算：data = x - min; min' = x' - data; 前后的 x' = min；
top：取栈顶，也是分大于0和小于0；大于0，不是最小值，返回栈顶元素+min；小于0，是最小值，直接返回min
min：直接返回min就好了。

class MinStack {
    Deque deque = new ArrayDeque<>();
    long mn;
    /** initialize your data structure here. */
    public MinStack() {

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

    }
    
    public void pop() {
        if(deque.isEmpty()) return;
        long temp = deque.removeFirst();
        if(temp < 0) {
            mn -= temp; 
        }
    }
    
    public int top() {
        long temp = deque.peekFirst();
        if(temp < 0) return (int)mn;
        return (int)(temp + mn);
    }
    
    public int min() {
        return (int)mn;
    }
}

0 赞同 0 条回复

June 普通 2023年7月12日上午10:01

class MinStack {

    public Stack<Integer> stack;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }
    //每次把当前最小的值压入栈顶
    public void push(int x) {
        if(stack.empty())
        {
            stack.push(x);
            stack.push(x);
        }
        else
        {
            int minNum = stack.peek();
            minNum = Math.min(minNum, x);
            stack.push(x);
            stack.push(minNum);
        }
    }

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

    public int top() {
        int tmp = stack.peek();
        stack.pop();
        int top = stack.peek();
        stack.push(tmp);
        return top;
    }

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

H、普通 2023年7月12日上午9:14

最小函数栈

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

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

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

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

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月11日下午11:49

Day5
//Java 代码中，由于 Stack 中存储的是 int 的包装类 Integer ，因此需要使用 equals() 代替来比较值是否相等。此题如果用将会无法通过 Integer的equals重写过，比较的是内部value的值，如果在[-128,127]会被cache缓存,超过这个范围则比较的是对象是否相同。

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

艺普通 2023年7月11日下午11:46

“`c++
//时间复杂度：O(1)
//空间复杂度：O(N)
class MinStack {
public:
stack s;
stack Mins;
/** initialize your data structure here. */
MinStack() {

}

void push(int x) {

if(s.empty())
{
s.push(x);
Mins.push(x);
return;
}
int prevMin = Mins.top();
int curMin = x < prevMin ? x : prevMin;
s.push(x);
Mins.push(curMin);
}

void pop() {

s.pop();
Mins.pop();
}

int top() {

return s.top();
}

int min() {

return Mins.top();
}
};

0 赞同 0 条回复

wonderful 普通 2023年7月11日下午11:16

用列表模拟栈
class MinStack:

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

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

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

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

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

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

普通 2023年7月11日下午11:08

c++代码维护一个栈顶为最小值的最小栈
class MinStack {
stack instack,minstack;//最小栈维护栈顶为最小值
public:
/** initialize your data structure here. */
MinStack() {

}

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

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

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

};

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月11日下午10:29

代码如下

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

0 赞同 0 条回复

远行客普通 2023年7月11日下午10:02

class MinStack:
    def __init__(self):
        # 元素栈
        self.stack = []
        # 辅助栈
        self.min_stack = []

    def push(self, x):
        # 有元素入栈时，
        # 该元素与辅助栈的栈顶的代表最小值的元素进行比较
        # 把最小值压入辅助栈
        self.stack.append(x)
        if len(self.min_stack) > 0:
            self.min_stack.append(min(x, self.min_stack[-1]))
        else:
            self.min_stack.append(x)

    def pop(self):
        # 有元素出栈时，辅助栈内的元素也一并出栈
        self.stack.pop()
        self.min_stack.pop()

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

    def min(self):
        # 任何时刻， 栈内最小元素就是辅助栈的栈顶元素
        return self.min_stack[-1]


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

0 赞同 0 条回复

ONE PIECE 普通 2023年7月11日下午9:39

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.pop().equals(stack2.peek())){
            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 条回复

阿尚普通 2023年7月11日下午7:20

//一个栈实现
class MinStack {
    Stack<Integer> stack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }

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

    public void pop() {
        if(stack.isEmpty()) return;
        stack.pop();
        stack.pop();
    }

    public int top() {
        int minVal = stack.pop();
        int topVal = stack.peek();
        stack.push(minVal);
        return topVal;
    }

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

V2ero 普通 2023年7月11日下午6:46

class Stack {
    private arr: number[];

    constructor() {
        this.arr = [];
    }

    push(x: number) {
        this.arr.push(x);
    }

    pop() {
        return this.arr.pop();
    }

    top() {
        return this.arr[this.arr.length - 1];
    }
}

/**
 * 辅助栈
 */
class MinStack {
    minStack: Stack;
    stack: Stack;
    constructor() {
        this.stack = new Stack();
        this.minStack = new Stack();
        this.minStack.push(Infinity);
    }

    push(x: number): void {
        this.stack.push(x);
        this.minStack.push(Math.min(x, this.minStack.top()));
    }

    pop(): void {
        this.stack.pop();
        this.minStack.pop();
    }

    top(): number {
        return this.stack.top();
    }

    min(): number {
        return this.minStack.top();
    }
}

0 赞同 0 条回复

Luminous 普通 2023年7月11日下午6:03

class MinStack {

    Stack<Integer> stack1;
    Stack<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
        stack1=new Stack<Integer>();
        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.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)

0 赞同 0 条回复

doordie. 普通 2023年7月11日下午4:35

通过额外的一个辅助栈解决问题

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

0 赞同 0 条回复

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

class MinStack {
    // 辅助栈解决
    /** initialize your data structure here. */
    Deque<Integer> xStack;
        Deque<Integer> minStack;

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

Mooby 普通 2023年7月11日下午3:33

五
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()) {
        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 条回复

桎梏普通 2023年7月11日下午3:33

辅助栈法

class MinStack {

    //定义两个栈 一个是仅存储最小值 一个存储所有值
    Stack<Integer> stack;
    Stack<Integer> minStack;

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

    public void push(int val) {
        //普通栈正常入 
        stack.push(val);
        if(minStack.isEmpty() || val <= minStack.peek()) {
            //最小栈如果为空 或小于等于栈顶时 入栈
            minStack.push(val);
        }
    }

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

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

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

0 赞同 0 条回复

小季同学普通 2023年7月11日下午3:07

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

class MinStack {
    // 正常入栈元素
    private stack1: number[] = []
    // 比上一个小则入栈
    private stack2: number[] = []
    constructor() {
    }

    push(x: number): void {
        // 第一次1 2栈都进入，后面，1正常压栈，2的话比上一个小或者等于则入栈
        if(this.stack1.length === 0) {
            this.stack2.push(x)
        } else {
            if( x <= this.stack2 [this.stack2.length - 1]) {
                this.stack2.push(x)
            }
        }
        this.stack1.push(x)
    }

    pop(): void {
        // 1 正常弹栈，2如果和1弹栈值相等也弹栈，否则不动
        // 边界判断
        if(this.stack1.length) {
            const result = this.stack1.pop()
        if(result === this.stack2[this.stack2.length - 1]) {
            this.stack2.pop()
        }
        }
    }

    top(): number {
        return this.stack1[this.stack1.length - 1]
    }

    min(): number {
        return this.stack2[this.stack2.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 条回复

CKX 普通 2023年7月11日下午3:06

type MinStack struct {
    stack []int
    //建立辅助栈
    minStack []int
}


/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{
        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
}

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

0 赞同 0 条回复

波雅汉库克普通 2023年7月11日下午3:05

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

    MinStack() {}

    void push(int val) {
        if(stk.empty()){
            stk.push(val);
            minStk.push(val);
            return;
        }
        int prevMin = minStk.top();
        int curMin = val < prevMin ? val : prevMin;
        stk.push(val);
        minStk.push(curMin);
    }

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

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

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

时间：O（1）
空间： O（n)

0 赞同 0 条回复

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

共以下 44 个回答

辅助栈

差值存储（单栈）

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

# 回答此问题取消回复

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

共以下 44 个回答

辅助栈

差值存储（单栈）

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

# 回答此问题 取消回复

# 回答此问题取消回复