【基本数据结构】剑指 Offer 30. 包含min函数的栈-跟着帅地玩副业，开拓第二曲线PlayOffer

yelinliner 普通 2024年12月4日下午9:17


class MinStack {
    // 正常栈
    private Stack stack1;
    // 存放最小元素栈
    private Stack stack2;

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

    public void push(int x) {
        // 栈1正常入栈
        stack1.push(x);
        // 栈2存储最小元素
        if (stack2.isEmpty() || x <= stack2.peek()) {
            stack2.push(x);
        }
    }

    public void pop() {
        // 判断栈2是否出栈
        if (stack1.peek().intValue() == stack2.peek().intValue()) {
            stack2.pop();
        }
        // 栈1正常出栈
        stack1.pop();
    }

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

    }

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

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

0 赞同 0 条回复

Lil Lee_ 普通 2024年12月3日下午11:00

//辅助栈法
class MinStack {

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

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

    public void pop() {
        if(a.pop().equals(b.peek()))
            b.pop();        
    }

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

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

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

0 赞同 0 条回复

岱永久会员 2024年12月2日下午4:10

用两个栈来实现

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 getMin() {
        return B.peek();
    }
}

0 赞同 0 条回复

陆狗陆狗普通 2024年11月30日下午9:53

class MinStack {

    // 【错误点】，没有定义泛型的类型
    private Stack<Integer> normalStack;
    private Stack<Integer> minStack;

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

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

    public void pop() {
        int val=normalStack.pop();
        if(minStack.peek()==val){
            minStack.pop();
        }
    }

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

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

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午8:05

/**
解题思路：
雇佣一个辅助栈维护当前值和之前入栈的最小值，每次入栈，出栈，取最小值时间复杂度O(1), 空间复杂度O(N)

 */
class MinStack {

    Deque<Integer> min;
    Deque<Integer> st;

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

    public void push(int x) {
        st.add(x);
        if (min.isEmpty() || min.getLast() > x){
            min.add(x);
        } else{
            min.add(min.getLast());
        }

    }

    public void pop() {
        st.pollLast();
        min.pollLast();
    }

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

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

0 赞同 0 条回复

Firefly 普通 2024年11月30日下午2:53

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

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

void pop() 
{
    if(m_sk1.top()==m_sk2.top())m_sk2.pop();
     m_sk1.pop();
}

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

int getMin() {

    return m_sk2.top();
}

private:
std::stack m_sk1;
std::stack m_sk2;
;
int m_nMinVal;
};

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

🌟 普通 2024年11月27日下午3:10

“`cpp;
中文
class MinStack {
std::stack s;
std::stack min;
public:
/** initialize your data structure here. */
MinStack() {}

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

void pop() {
    int val = s.top();
    s.pop();
    if (!min.empty() && val == min.top()) {
        min.pop();
    }
}

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

int getMin() {
    if (!min.empty()) {
        return min.top();
    }
    return INT_MAX; 
}

};

0 赞同 0 条回复

Tom Yuan 普通 2024年11月27日上午5:52

思路：用两个辅助stack 一个存储所有的值另一个每次push时记录当前遇到的最小值
这样可以保证第二个stack里能每次都很快的取得最小值

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        # add a really large number for initial compare
        self.min_stack = [math.inf]

    def push(self, x: int) -> None:
        # with the idea that the min will always be at top.
        # then always add the existing min value
        # into the actual min_stack.
        self.stack.append(x)
        self.min_stack.append(min(x, self.min_stack[-1]))

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

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

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

time O(1) space O(n) worst case O(2n).

0 赞同 0 条回复

Jerry 普通 2024年11月26日下午3:43

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

    }

    void push(int x) {
        valstack.push(x);
        if(minvalstack.empty()){
            minvalstack.push(x);
        }
        else if(!minvalstack.empty()){
            if(x <= minvalstack.top()){
                minvalstack.push(x);
            }
        }

    }

    void pop() {
        int tmp = valstack.top();
        valstack.pop();
        if(tmp == minvalstack.top()){
            minvalstack.pop();
        }
    }

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

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

思路：创建两个stack，其中一个栈（valstack）存储原始元素，一个栈（minvalstack）用来存储元素后的最小元素
时间：o(1)
空间：o(n)

0 赞同 0 条回复

生活在经验里普通 2024年11月26日下午3:40

// 创建两个栈，一个栈主栈 stack; 一个辅助栈 min_slice: 存放对应主栈不同时期的最小值
type MinStack struct {
    slice     []int
    min_slice []int
}

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

func (this *MinStack) Push(x int) {
    this.slice = append(this.slice, x)
    if len(this.min_slice) == 0 {
        this.min_slice = append(this.min_slice, x)
    } else {
        cur_min := min(x, this.min_slice[len(this.min_slice)-1])
        this.min_slice = append(this.min_slice, cur_min)
    }
}

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

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

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

0 赞同 0 条回复

越努力越幸运普通 2024年11月26日上午12:40

“`c++
class MinStack {
public:
MinStack() {

}

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

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

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

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

private:
stack stack1, stack2;
};
//打卡

“`

0 赞同 0 条回复

休一普通 2024年11月25日下午10:30

1.思路分析

核心思路

双栈设计：
– 一个栈（stNormal）用于存储所有插入的元素，记录栈的完整数据。
– 另一个栈（stMin）用于存储每一步的最小值，记录当前栈的最小元素。
辅助栈的作用：
– 每次入栈操作时，辅助栈更新记录当前栈的最小值。
– 每次出栈操作时，辅助栈同步出栈，保证 stMin 栈顶始终是当前栈中最小的元素。

2.代码分析

class MinStack {
private:
    stack stackNormal;
    stack stackMin;
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        int temp = x;
        stackNormal.push(temp);
        if(!stackMin.empty())
        {
            temp = min(temp,stackMin.top());
        }
        stackMin.push(temp);
    }

    void pop() {
        stackMin.pop();
        stackNormal.pop();
    }

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

    int getMin() {
         return stackMin.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->getMin();
 */

3.复杂度分析

时间复杂度均为o(1)
空间复杂度为o(n)，因为设置了一个辅助栈用于建立最小栈。

0 赞同 0 条回复

mpweixin用户普通 2024年11月25日下午9:37

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

    }

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

    void pop() {
        int temp1 = base.top();
        base.pop();
        int temp2 = min_stack.top();
        if(temp1 == temp2){
            min_stack.pop();
        }
    }

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

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

思路：用一个栈专门存截止到当前入栈元素为止，降序元素的顺序。
时间O(1)，空间O(N)

0 赞同 0 条回复

lQl 永久会员 2024年11月25日下午9:12

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

class MinStack {
    Stack<Integer> s;
    Stack<Integer> min;

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

        min.push(Integer.MAX_VALUE);
    }

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

        s.push(x);
    }

    public void pop() {
        if(s.peek().equals(min.peek())){
            min.pop();
        }
        s.pop();
    }

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

    public int getMin() {
        return min.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.getMin();
 */

0 赞同 0 条回复

张君雅小妹妹普通 2024年11月25日下午8:31

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> help; // 定义一个辅助栈

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

    public void push(int x) {
        stack.push(x);
        if(help.isEmpty()){
            help.push(x);
        } else {
            int min = x < help.peek() ? x : help.peek();
            help.push(min);        
        }
    }

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

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

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

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

0 赞同 0 条回复

秋山丽奈普通 2024年11月25日下午7:59

思路: 使用两个栈，一个栈正常记录元素，一个栈记录当前最小值：多当前元素小于栈顶，则当前元素为最小值，否则栈顶元素做为最小值

class MinStack {

    /** initialize your data structure here. */
    // 维护一个 单调栈 
    Stack<Integer> stack;
    Stack<Integer> singleStack;

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

    public void push(int x) {
        // 将元素 插入 栈 
        this.stack.push(x);

        // 将元素 插入 单调栈 
        int currrent = this.singleStack.peek();
        if(currrent >= x){
            // 当前元素 即为 最小 
            this.singleStack.push(x); 
        }else{
            this.singleStack.push(currrent); 
        }


    }

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

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

    public int getMin() {
        return this.singleStack.peek();
    }
}

0 赞同 0 条回复

Pendulumpal 普通 2024年11月25日下午4:55

在构建栈的时候，用辅助栈维护最小值

“`c++
class MinStack {
public:
/** initialize your data structure here. */
stacksk;
stackhelp;
MinStack() {

}

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

void pop() {
    int tp=sk.top();
    sk.pop();
    if(tp==help.top()){
        help.pop();
    }
}

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

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

};

“`

0 赞同 0 条回复

Kisara 普通 2024年11月25日下午3:26

没有学过算法，初步写了一个通过用例但是时间超时的答案

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

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

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

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

    public int getMin() {
        min=stack1.peek();
        while(!stack1.empty()){
            if(stack1.peek()

解决方法：
方法一，空间大时间短，一开始写完不知道错在哪里，后来发现没有拆箱integer，导致有错误时间O（1）空间O（N）

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

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

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

    public int top() {
        return stack1.peek().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();
 */

方法二：时间长空间小，直接遍历全栈，寻找最小值，用stack的迭代器时间O（N）空间O（1）

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

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

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

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

    public int getMin() {
        int min=stack.peek().intValue();
        Iterator value=stack.iterator();
        while(value.hasNext()){
            Integer current=(Integer)value.next();
            if(current.intValue()

0 赞同 0 条回复

无言永久会员 2024年11月25日下午3:10

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stk;
    stack<int> minStk; // 存储当前栈内元素的最小值
    MinStack() {

    }

    void push(int x) {
        stk.push(x);
        // 当新元素入栈时，更新当前栈内的最小值，并记录在minStk中
        if(!minStk.empty()) {
            minStk.push(min(x, minStk.top()));
        } else {
            minStk.push(x);
        }
    }

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

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

    int getMin() {
        return minStk.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->getMin();
 */
时间复杂度: O(1) 
空间复杂度: O(n)

0 赞同 0 条回复

月下足迹普通 2024年11月25日下午1:42

//设置一个保存最小值变化的栈
class MinStack {

    Stack<Integer> stack;
    Stack<Integer> minstack;
    Integer minnum;

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

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

    public void pop() {
        if (stack.isEmpty()) {
            return;
        }
        if(stack.peek().equals(minstack.peek())) {
            minstack.pop();
            minnum = minstack.isEmpty()? Integer.MAX_VALUE : minstack.peek();
        }
        stack.pop();
    }

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

    public int getMin() {
        return minnum;
    }
}

0 赞同 0 条回复

黑键〰普通 2024年11月25日下午12:31

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

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack1.push(x)
    if(!this.stack2.length || x <= this.stack2.slice(-1)[0]) {
        this.stack2.push(x)
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    if(this.stack1.length) {
        if(this.stack1.slice(-1)[0] == this.stack2.slice(-1)[0]) {
            this.stack2.pop()
        }
        this.stack1.pop()
    }
};

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

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.stack2.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.getMin()
 */

看完解题视频之后理清了思路，第二个栈用来依次存放相对当前栈顶更小的数值，每次pop操作的时候会检查一下是否把当前最小值pop出去了，和第一个栈的状态始终保持一致，所以可以在O(1)的时间复杂度来找到min值

0 赞同 0 条回复

苯庸普通 2024年11月25日上午10:21

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.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 getMin() {
    return s2.peek();
}

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

0 赞同 0 条回复

Renasc 普通 2024年11月25日上午10:03

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
        A.push(x);
        // 如果栈B为空，或者顶部元素小于x，则入栈B
        if (B.isEmpty() || x <= B.peek()) {   // peek是只输出栈顶元素，不删除； pop是输出栈顶元素并删除
            B.push(x);
        }
    }

    public void pop() {
        // A先出栈
        Integer y = A.pop();
        // 若B的栈顶元素等于A的栈顶元素，则一起删除
        if (y.equals(B.peek())) {     // 这里不能用 == 
            B.pop();
        }
    }

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

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

0 赞同 0 条回复

Xiang. 永久会员 2024年11月25日上午9:31

思路：定义两个栈A、B，A实现栈的正常存取，B中存入符合A存取顺序的最小值，实现getMin
class MinStack {
    Stack<Integer> A;
    Stack<Integer> B;
    /** initialize your data structure here. */
    public MinStack() {
        A=new Stack<>();
        B=new Stack<>();
    }

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

    public void pop() {
        int x=A.pop();
        if(x==B.peek()) B.pop();
    }

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

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

0 赞同 0 条回复

youngsir 普通 2024年11月25日上午9:03

打卡，维护两个栈一个存放全部值一个存放最小值。

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

    }

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

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

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

    }
};

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

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

0 赞同 0 条回复

jaron 普通 2024年11月24日下午10:27

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

class MinStack {

    Stack<Integer> data;
    Stack<Integer> min;

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

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

    public void pop() {
        if (!data.isEmpty()) {
            if (data.peek().equals(min.peek())) {
                min.pop();
            }
            data.pop();
        }
    }

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

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

0 赞同 0 条回复

晓宇普通 2024年11月24日下午7:57

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

    }

    void push(int x) {
        normalS.push(x);
        if(minS.empty()) minS.push(x);
        else if(x <= minS.top()) minS.push(x);
        return ;
    }

    void pop() {
        if(normalS.empty()) return ;
        int x = normalS.top();
        normalS.pop();
        if(x == minS.top()) minS.pop();
        return ;
    }

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

    int getMin() {
        if(minS.empty()) return -1;
        return minS.top();
    }
};
 // 思路：另维护一个存放最小值的栈
 // 时间复杂度o(1); 空间复杂度o(n)

0 赞同 0 条回复

迢迢星野普通 2024年11月24日下午7:34

class MinStack {
    // 两个栈
    Stack<Long> stack;
    Stack<Long> min;

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

    public void push(long x) {
        if (stack.isEmpty()) {
            min.push(x);
            stack.push(x);
            return;
        }
        stack.push(x);
        min.push(Math.min(x, min.peek()));
    }

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

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

    public long getMin() {
        return min.peek();
    }
}

思路：通过维护两个栈，一个存储所有元素，另一个存储当前的最小值，可以在常数时间内完成所有操作。
时间复杂度：所有的操作的时间复杂度均为 O(1)。
空间复杂度：O(n)，需要额外的空间来存储最小值。

0 赞同 0 条回复

🍊 普通 2024年11月24日下午7:15

一个最小值辅助栈即可
class MinStack {
Stack stk = new Stack<>(), min = new Stack<>();

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

}

public void push(int x) {
    if(stk.isEmpty()){
        stk.push(x);
        min.push(x);
        return;
    }
    stk.push(x);
    min.push(Math.min(min.peek(), x));
}

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

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

public int getMin() {
    return min.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.getMin();
*/

0 赞同 0 条回复

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

共以下 29 个回答

1.思路分析

核心思路

2.代码分析

3.复杂度分析

# 回答此问题取消回复

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

共以下 29 个回答

1.思路分析

核心思路

2.代码分析

3.复杂度分析

# 回答此问题 取消回复

# 回答此问题取消回复