当前位置：
  1. 首页
  2. 剑指offer刷题第五期
  3. 问题详情

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

本问题对应课程链接：剑指offer刷题第五期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
343 28

共以下 28 个回答

  • 谁仁 普通 2023年9月5日 下午5:25

    #include<stdio.h>
    #include<stdlib.h>

    typedef struct StackNode
    {
    int data;
    int min;
    struct StackNode * next;
    }StackNode;

    typedef struct MinStack
    {
    StackNode * top;
    }MinStack;

    MinStack * init_MinStack()//初始化栈
    {
    MinStack * stack = (MinStack *)malloc(sizeof(MinStack));
    stack->top = NULL;
    return stack;
    }

    int isEmpty(MinStack * stack)//判断是否为空栈
    {
    return stack->top NULL;
    }

    void push(MinStack * stack , int value)//入栈
    {
    StackNodenewNode = (StackNode)malloc(sizeof(StackNode));
    newNode->data = value;
    if(isEmpty(stack))
    {
    newNode->min = value;
    }
    else
    {
    int currentMin stack->top->min;
    newNode->min = (value<currentMin)? value:currentMin;
    }

    newNode->next = stack->top;
stack->top = newNode;

    }

    int pop(MinStack *stack)//出栈
    {
    if(isEmpty(stack))
    {
    printf(” error: stack is empty\n”);
    return -1;
    }
    StackNode * tmp = stack->top;
    int popValue = tmp->data;
    stack->top = tmp->next;
    free(tmp);
    return popValue;
    }

    int top(MinStack * stack)//打印栈顶
    {
    if(isEmpty(stack))
    {
    printf(” error: stack is empty\n”);
    return -1;
    }

    return stack->top->data;

    }

    int getMin(MinStack * stack)//获取最小栈
    {
    if(isEmpty(stack))
    {
    printf(” error: stack is empty\n”);
    return -1;
    }
    return stack->top->min;

    }

    void freeMinStack(MinStack * stack)//释放栈
    {
    while(!isEmpty(stack))
    {
    pop(stack);
    }
    free(stack);
    }
    //总体时间复杂度o（1），空间复杂度o（1）

    0 赞同 0 条回复
  • QQiing 普通 2023年9月4日 上午9:32

    class MinStack {
    public:
    /** initialize your data structure here. */
    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;
}

    private:
    stack s1, s2;
    };

    /**
    * 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年8月29日 下午9:06

    打卡

    class MinStack {
public:
    stack<int> s1;//栈1保存所有元素
    stack<int> s2;//栈2保存min元素
    /** initialize your data structure here. */
    MinStack() {

    }

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

    void pop() {
        int x = s1.top();
        if(x == s2.top()){//此时要删除的元素在栈1栈2都有
            s2.pop();
        }
        s1.pop();
    }

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

    int min() {
        return s2.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年8月27日 下午8:51

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

    思路

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

    解题思路

    1. 第一种方法是使用两个栈来实现，用一个栈去存放对应的数据，用另一个栈去存放当前的最小值，在调用min()函数的时候，直接返回最小栈的数据即可
      1. 题解动画详解 剑指 Offer 30. 包含min函数的栈 – 力扣（LeetCode）
    2. 第二种方法是使用一个栈和一个最小值变量，用变量存放着最小值，用栈存放着当前插入数据与最小值的差值，在弹出数据的时候经过处理返回栈内的元素，当获取最小值的时候，直接返回单独的最小值变量

    解题方法1

    解题方法

    1. 这里需要在pop和push的时候做特殊的处理，在push的时候，如果最小栈中没有元素，说明两个栈都是插入的第一个元素，所以两个栈中都要存放当前插入的x,如果在push的时候，新插入的数据值小于等于minStack栈顶的元素时候，需要在minStack中也插入当前值，表明这是最小值
      1. 因为一开始只写了< 没有写等于号，对于重复的数据没有插入到minStack中导致在最后调用min()函数的时候导致栈空异常了
    2. 在两个栈的时候，pop的时候，如果弹出的元素是minStack的栈顶元素 说明弹出的元素是当前的最小值，所以需要将minStack的栈顶元素弹出

    复杂度

    时间复杂度:

    时间复杂度： $O(n)$

    空间复杂度:

    空间复杂度： $O(n)$

    Code（自己写的）

    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(stack.isEmpty()){
            stack.push(x);
            minStack.push(x);
        }else{
            stack.push(x);
        }
        if(x <= minStack.peek()){// 这里不能只在小于的时候加入到min栈，需要设定<=
        // 因为题目中没有说明不插入重复的数据，一开始在提交的时候，因为重复数据提交不通过
            minStack.push(x);
        }


    }

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

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

    }

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

    Code（标准简化的）

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

作者：Krahets
链接：https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/solutions/133760/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    帅地版本

    帅地版本在设定的时候，因为Integer的范围是（-127——127） 所以使用intValue()函数进行下处理 

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

    解题方法2（待补充）

    解题方法

    1. 这里需要在pop和push的时候做特殊的处理，在push的时候，如果最小栈中没有元素，说明两个栈都是插入的第一个元素，所以两个栈中都要存放当前插入的x,如果在push的时候，新插入的数据值小于等于minStack栈顶的元素时候，需要在minStack中也插入当前值，表明这是最小值
      1. 因为一开始只写了< 没有写等于号，对于重复的数据没有插入到minStack中导致在最后调用min()函数的时候导致栈空异常了
    2. 在两个栈的时候，pop的时候，如果弹出的元素是minStack的栈顶元素 说明弹出的元素是当前的最小值，所以需要将minStack的栈顶元素弹出

    复杂度

    时间复杂度:

    时间复杂度： $O(n)$

    空间复杂度:

    空间复杂度： $O(n)$

    Code

    0 赞同 0 条回复
  • 漂洋过海去见你 永久会员 2023年8月27日 下午4:56

    #python题解：
    #空间复杂度：n
    #时间复杂度：1
    class MinStack(object):

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


def push(self, x):
    """
    :type x: int
    :rtype: None
    """
    self.stack1.append(x)

    if len(self.stack2) == 0 or (self.stack2[-1] >= x):
        self.stack2.append(x)


def pop(self):
    """
    :rtype: None
    """
    if len(self.stack1) == 0:
        return None
    cur = self.stack1.pop()

    if cur == self.stack2[-1]:
        self.stack2.pop()
    return cur



def top(self):
    """
    :rtype: int
    """
    if len(self.stack1) == 0:
        return None
    return self.stack1[-1]



def min(self):
    """
    :rtype: int
    """
    return self.stack2[-1]
    0 赞同 0 条回复
  • Di questa storia sempre a lie to 普通 2023年8月25日 下午4:59

    class MinStack {
    std::stack s1{}, s2{};
    public:
    /** initialize your data structure here. */
    MinStack() {
    s2.push(INT_MAX);
    }

    void push(int x) {
   s1.push(x);
   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();
}

    };
    时间复杂度：o(n）
    空间复杂度：o(n)

    0 赞同 0 条回复
  • Miracle· 普通 2023年8月24日 下午8:16

    class MinStack {
    stack restack, minstack; // minstack负责存放最小元素
    public:
    /** initialize your data structure here. */
    MinStack() {

    }

void push(int x) {
    restack.push(x);
    if (minstack.empty()) {
        minstack.push(x);
    }
    else {
        int temp = minstack.top();
        if (temp > x) {
            minstack.push(x);
        }
        else {
            minstack.push(temp);
        }
    }
}

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

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

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

    };

    0 赞同 0 条回复
  • mpweixin用户 普通 2023年8月24日 下午4:59

    //采用辅助栈的方法，第二栈用于存储最小的值;
    //插入和删除时间复杂度都为o(1);
    //空间复杂度为o(n);

    class MinStack {
    public:
    /** initialize your data structure here. */
    stack stack1;
    stack     stack2;//辅助栈

    MinStack() {
    stack2.push(INT_MAX);

}
void push(int x) {
    stack1.push(x);
    stack2.push(::min(stack2.top(),x));

}

void pop() {
    stack1.pop();
    stack2.pop();
}

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

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

    };

    0 赞同 0 条回复
  • sc_Yang 普通 2023年8月22日 下午11:43 
    // 使用一个完全存储最小值的栈作为min函数的返回值
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s;
    stack<int> min_stack;
    // int minValue = INT_MAX; 
    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());
        }
        s.push(x);
    }

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

    int top() {
        return s.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 条回复
  • 💮黧大王.exe 普通 2023年8月21日 下午2:35

    时间复杂度：O(1)
    空间复杂度：O(n)
    class MinStack {
    public:
    /** initialize your data structure here. */
    stack stack1;
    stack     stack2;
    MinStack() {

    }

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

void pop() {
    int r=stack1.top();
    stack1.pop();
    if(r==stack2.top())
    stack2.pop();
}

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

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

    };

    0 赞同 0 条回复
  • 辰北、 普通 2023年8月20日 下午4:20

    //一个辅助栈p-Min，初始都存入第一个数，后面每放进一个数，与x比大小，min栈栈顶小的话，下一元素存入min栈顶值，x小存x，总是min栈和原始栈一样多的元素，增加的话需要判断自身和x，小者存入；删的话都–；查的话，原始栈顶返回top；min值就返回mintop值；free就双栈都释放；
    typedef struct {
    int top;
    int min_top;
    int *stack;
    int *min_stack;
    } MinStack;

    /** initialize your data structure here. */

    MinStack* minStackCreate() {
    MinStack* obj = (MinStack *)malloc(sizeof(MinStack));
    obj->stack = (int *)malloc(sizeof(int) * 10000);
    obj->min_stack = (int *)malloc(sizeof(int) * 10000);
    obj->top = -1;
    obj->min_top = -1;
    return obj;
    }

    void minStackPush(MinStack* obj, int x) {
    obj->stack[++obj->top] = x;//将x入栈stack
    // if(obj->min_top -1)//若栈min_stack为空，将x入栈
    // obj->min_stack[++obj->min_top] = x;
    // else if(obj->min_stack[obj->min_top] >= x)//x小于等于栈min_stack的栈顶元素，则将x入栈
    // obj->min_stack[++obj->min_top] = x;
    if(obj->min_top     -1)//若栈min_stack为空，将x入栈
    obj->min_stack[++obj->min_top] = x;
    else{
    if(obj->min_stack[obj->min_top] >= x){
    obj->min_stack[++obj->min_top] = x;
    }
    else{
    obj->min_stack[++obj->min_top] = obj->min_stack[obj->min_top] ;
    }

        }

    }

    void minStackPop(MinStack* obj) {

        obj->top--;
    obj->min_top--;

    }

    int minStackTop(MinStack* obj) {
    return obj->stack[obj->top];//top函数返回栈的栈顶元素，所以返回stack的栈顶元素
    }

    int minStackMin(MinStack* obj) {
    return obj->min_stack[obj->min_top];//min函数返回栈的最小元素，所以返回min_stack的栈顶元素
    }

    void minStackFree(MinStack* obj) {
    free(obj->stack);
    free(obj->min_stack);
    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 条回复
  • Marc 普通 2023年8月19日 下午11:21 
    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 self.stack2:
            self.stack2.append(min(self.stack2[-1], x))
        else:
            self.stack2.append(x) 

    def pop(self) -> None:
        self.stack1.pop()
        self.stack2.pop()

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

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

    时间O(1)空间O(N)

    0 赞同 0 条回复
  • 天亮说晚安 普通 2023年8月19日 下午5:30

    暴力解法

    lass MinStack {
    Stack A;
    Stack B;
    Integer minNum ;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
        minNum = Integer.MAX_VALUE;
    }


    public void push(int val) {
    A.push(val);
    if(val
    

    }
    

    

    时间复杂度O(n)，空间复杂度O(N)
    0 赞同 0 条回复
  • Sheng 永久会员 2023年8月19日 下午5:08

    直接看的解答代码
    ”’java
    import java.util.Stack;
    //定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min()函数
    //并且调用min push pop 的时间复杂度都是O(1)
    //使用两个栈，一个是正常的，一个放置最小元素，每次push都将更小的元素放进去，pop的时候判断是否出栈
    class MinStack {
    Stack stack1;
    Stack     stack2;
    public MinStack() {
    this.stack1 = new Stack    ();
    this.stack2 = new Stack    ();//存放所有最小值
    }

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

    //这一句包含两种场景：（stack2为空） 和 （stack2不为空，且栈顶元素大于等于x）
    if(stack2.empty() || x <= stack2.peek().intValue()) {//这一句包含两种场景
        stack2.push(x);
    }
}

public void pop() {
    if(!stack1.empty()) {
        //Integer ,数值大于127的时候比较的是对象
        //百度搜一下Integer的自动装箱
        //Integer ,数值小于127的时候比较的是常量池中元素的数值，
        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 条回复
  • Jou Siankwa 普通 2023年8月18日 下午9:34 
    class MinStack {

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

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

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

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

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

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.min());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.min());
    }
}

    用一个栈A存数据，用另一个栈B存储当前的最小值，如果栈A弹出的值正好是B的栈顶元素，B也弹出。

    0 赞同 0 条回复
  • 木子有点甜🍒 普通 2023年8月18日 下午8:53

    “`python
    #时间复杂度O(1)，牺牲了空间复杂度，没想到pop()里面还是用pop()
    class MinStack:

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


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

    self.stackA.append(x)


def pop(self) -> None:
    if self.stackA.pop() == self.stackB[-1]:
        self.stackB.pop()


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


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

    “`python

    0 赞同 0 条回复
  • 木木 普通 2023年8月18日 下午3:32

    時間複雜度 O(1) 空間複雜度 O(n)
    輔助棧

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

    }
    stack s;
    stack s_min;
    int val;
    
    void push(int x) {
      if (s.empty()) {
        s_min.push(x);
        val = x;
      } 
      else {
        val = x < val ? x : val;
        s_min.push(val);
      }
      s.push(x);

    }
    
    void pop() {
      if (!s.empty()) {
        s.pop();
        s_min.pop();
        if (!s_min.empty()) {
          val = s_min.top();
        }           
      } 
    }
    int top() {
      if (!s.empty()) {
        return s.top();
      }
      return -1;
    }
    
    int min() {
      return s_min.top();
    }
};

    空間複雜度 O(1) 解法
    儲存 min跟壓入值的差值, 只要儲存的值小於0則表示該差值對應的原始值為當前的最小值

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

    }

    stack s;
    long long min_val = 0;

    void push(int x) {
      if (s.empty()) {
        min_val = x;
        s.push(0);
      }
      else {
        long long delta = x - min_val;
        s.push(delta);
        min_val = delta < 0 ? x : min_val;
      }
    }
    
    void pop() {
      if (!s.empty()) {
        if ( s.top() < 0) {
        min_val = min_val - s.top();
        }
        s.pop();
      }
    }
   
    int top() {
        if (s.top() > 0) {
          return s.top() + min_val;
        }
        else {
          return min_val;
        }
    }
    int min() {
      return min_val;
    }
};
    0 赞同 0 条回复
  • 一个人的风海吹了两遍 普通 2023年8月18日 下午1:45

    刚开始想的是用第二个栈在求最小值时遍历一遍再放回第一个栈
    结果超时
    看了下讲解才明白
    但这行代码要加 .intValue()才没出错是我没想到的

    stack2.peek().intValue() == stack1.peek().intValue()

    class MinStack {

    /** initialize your data structure here. */


    Stack stack1;
    Stack stack2;

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

    //进栈
    public void push(int x) {
        if(stack1.isEmpty()){
            stack1.push(x);
            stack2.push(x);
        }else {
            stack1.push(x);
            if (x <= stack2.peek())
                stack2.push(x);
        }
    }
    //出栈
    public void pop() {
        if(stack2.peek().intValue()==stack1.peek().intValue()){
            stack2.pop();
            stack1.pop();
        }else {
            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年8月17日 下午9:58 
    class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.list = []
        self.min_list = []
        self.length  = 0


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        if self.length == 0:
            self.min_list.append(x)
        self.length+=1
        self.list.append(x)
        if x <= self.min_list[-1] and self.length >=1:
            self.min_list.append(x)


    def pop(self):
        """
        :rtype: None
        """
        if self.min_list[-1] == self.top():
            self.min_list.pop()
        self.length-=1
        return self.list.pop()


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

    def min(self):
        """
        :rtype: int
        """
        if not self.min_list:
            return 0
        return self.min_list[-1]

    使用最小栈

    0 赞同 0 条回复
  • Joel 普通 2023年8月17日 下午3:29

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

    class MinStack:

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

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

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

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

    def min(self) -> int:
        if len(self.minStack) == 0:
            return None
        return self.minStack[-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 条回复
  • sincere 普通 2023年8月17日 下午2:38
    • 思路：额外用一个 minStack 存储最小数值，minStack 只有在 push 的数值比栈顶小时才压入，弹出时，如果弹出元素等于 minStack 栈顶元素，minStack 也弹出，相当于更新最小值
    • 复杂度：时间复杂度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.isEmpty() || minStack.peek() >= x) {
            minStack.push(x);
        }
    }

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

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

    public int min() {
        return minStack.peek();
    }
}
    0 赞同 0 条回复
  • mpweixin用户 永久会员 2023年8月17日 下午2:26

    一个普通栈一个保存当前元素前最小值的栈

    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.peek().intValue() == stack2.peek().intValue()) {
            stack2.pop();
        }
        stack1.pop();
    }

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

    public int min() {
        return stack2.peek();
    }
}
    0 赞同 0 条回复
  • mpweixin用户 永久会员 2023年8月17日 上午11:49 
    // 一个正常栈，一个保存当前栈中最小值
class MinStack {
private:
    stack<int> stk;
    stack<int> minStk;
public:
    /** initialize your data structure here. */
    MinStack() {
        minStk.push(INT_MAX);
    }

    void push(int x) {
        stk.push(x);
        minStk.push(std::min(minStk.top(), x));
    }

    void pop() {
        if(!stk.empty()){
            stk.pop();
        }
        if(!minStk.empty()){
            minStk.pop();
        }
    }

    int top() {
        if(!stk.empty()){
            return stk.top();
        }
        else return -1;
    }

    int min() {
        return minStk.top();
    }
};
    0 赞同 0 条回复
  • 行动派小彩笔 普通 2023年8月16日 下午9:12 
    // 利用辅助栈，时间O(1),空间O(n)
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stack1; //正常栈
    stack<int> stack2; //最小栈

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

    void push(int x) {
        stack1.push(x);
        stack2.push(std::min(stack2.top(),x));
    }

    void pop() {
        stack1.pop();
        stack2.pop();
    }

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

    int min() {
        return stack2.top();
    }
};
    0 赞同 0 条回复
  • JustRtn 普通 2023年8月16日 下午4:00 
    // 使用辅助栈存储栈当前top下的最小值
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        minStk.push(INT_MAX);
    }

    void push(int x) {
        stack.push(x);
        int minVal = ::min(x, minStk.top());
        minStk.push(minVal);
    }

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

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

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

// 差值法
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        if (stack.empty()) {
            minVal = x;
            stack.push(0);
            return ;
        }
        long tmp = x - minVal;
        if (tmp < 0) {
            minVal = x;
        }
        stack.push(tmp);
    }

    void pop() {
        if (stack.top() < 0) {
            minVal -= stack.top();
        }
        stack.pop();
    }

    int top() {
        if (stack.top() < 0) {
            return minVal;
        }
        return minVal + stack.top();
    }

    int min() {
        return minVal;
    }
private:
    std::stack<long> stack;
    long minVal { INT_MAX };
};
    0 赞同 0 条回复
  • 逸兴遄飞 普通 2023年8月16日 下午3:55

    辅助栈实现
    + 空间复杂度：O(N)，
    + 时间复杂度： O(1)。

    class MinStack {
    // 初始化两个栈，1用于存储数值，2用于存储栈1的当前最小值
    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);
        // 栈2也压入第一个值；当压入栈1的数值小于之前的最小值时，一并压入栈2
        if(stack2.isEmpty() || x <= stack2.peek().intValue()){
            stack2.push(x);
        }
    }

    public void pop() {
        // 栈1还有值时，出栈操作
        if(!stack1.isEmpty()){
            // 判断出栈值是否为当前最小值，True则1和2一并出栈
            // 当压入的数值大小超过127时，peek操作读取的是对象比较会出错，所以强制转换为int数值
            if(stack1.peek().intValue() == stack2.peek().intValue()){
                stack2.pop();
            }
        }
        stack1.pop();
    }

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

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

    下面是保存差值法，不需要使用额外的栈。

    class MinStack {

    Stack stack;
    Long min;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }
    
    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0l);
            min = Long.valueOf(x);
        } else {
            stack.push((long) (x - min));
            min = Math.min(x, min);
        }
    }
    
    public void pop() {
        if (stack.peek() < 0) {
            min = min - stack.pop();
            return;
        }
        stack.pop();
    }
    
    public int top() {
        if (stack.peek() > 0) {
            return (int) (min + stack.peek());
        } else {
            return Math.toIntExact(min);
        }
    }
    
    public int min() {
        return Math.toIntExact(min);
    }
}
    0 赞同 0 条回复
  • 别扒拉我 普通 2023年8月16日 下午3:36

    1、辅助栈。把最小的那一个存入辅助栈。

    class MinStack {

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

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

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

    public void pop() {
        stack1.pop();
        stack2.pop();
    }

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

    public int min() {
        return stack2.peek();
    }
}
    0 赞同 0 条回复
  • c 普通 2023年8月16日 下午3:01

    辅助栈

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

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

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

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

    public int min() {
        return min.peek();
    }
}
    0 赞同 0 条回复

# 回答此问题

后才能回答