Laboratory 普通 2024年4月15日下午11:04

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

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

    public void push(int x) {
        stack.offerLast(x);
        if(minStack.isEmpty() || x <= minStack.peekLast()) {
            minStack.offerLast(x);
        }
    }

    public void pop() {
        int i = stack.pollLast();
        if(i == minStack.peekLast()) {
            minStack.pollLast();
        }
    }

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

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

/**
 * 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年3月16日下午3:47

// 最小栈元素，最开始冒出的解决办法是遍历一遍这个栈的元素，但是复杂度是O(n),降低复杂度的话需要借助辅助栈来存储最小元素
// 值得注意的点，也是我犯错误的栈b辅助栈中的元素存储的是“非严格降序的”元素，>=，而不是>
// 还有一个自己的思考误区，总认为栈中已经有元素了，要把栈中的最小值求出来，这样就完全想不到借用辅助栈的方法去解决问题

class MinStack {
public:
/** initialize your data structure here. */
//成员变量
stack a,b; // 维护两个栈
MinStack() {

}

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

}

void pop() {
    if(a.top() == b.top())
    {
        b.pop();
    }
     a.pop();

}

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

}

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

}

};

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

YOLO 普通 2024年3月14日上午9:32

//定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，
class MinStack {

    /** initialize your data structure here. */
    Stack<Integer>A,B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    //将x压入栈
    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()))//使用.equals判断相等值
            B.pop();

    }

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

    }

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

    }
}

0 赞同 0 条回复

！。！普通 2024年3月13日上午10:46

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

    }

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

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

    }

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

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

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

0 赞同 0 条回复

晚风、普通 2024年3月12日下午11:38

def init(self):
“””
initialize your data structure here.
“””
self.q1 = []
self.q2 = []

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

def pop(self) -> None:
    if self.q1.pop() == self.q2[-1]:
        self.q2.pop()

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

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

为了能够保证获取最小元素的时间复杂度为o(1)
需要在申请一个列表进行辅助，存储非严格递减数据
在push的时候需要确认辅助列表为空或者目前push的元素小于等于辅助栈的栈顶元素，将该元素也压入辅助栈
在pop的时候需要需要确认原始列表pop的内容是否等于辅助栈的栈顶元素，如果等于，则辅助栈的元素也要pop
时间复杂度：o(1)
空间复杂度：o(n)

0 赞同 0 条回复

一颗红豆普通 2024年3月11日上午10:58

核心思想是另外拿一个栈以存方最小值时间复杂度和空间复杂度均为o（1）
class MinStack {
public:
/** initialize your data structure here. */
stack s1;
stack s2;
MinStack() {
std::stack s1;
std::stack s2;
}

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

}

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

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


}

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

};

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

Fancy 普通 2024年3月11日上午10:53

class MinStack:
# 维护两个栈，原栈：正常push和pop；最小栈：存放小的但是后入栈的那些数
def init(self):
self.stack1 = []
self.stack2 = []

def push(self, x: int) -> None:
    if not self.stack1:
        self.stack1.append(x)
        self.stack2.append(x)
    elif self.stack2 and x <= self.stack2[-1]: #都不空 且出现更小的元素
        self.stack1.append(x)
        self.stack2.append(x)
    else:
        self.stack1.append(x)

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

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

def getMin(self) -> int:
    if self.stack2:
        return self.stack2[-1]
    else:
        return self.stack1[-1]

0 赞同 0 条回复

MARS 普通 2024年3月9日下午11:51

day5第一题

class MinStack {
    stack: number[]
    minStack: number[]
    constructor() {
        this.stack = []
        this.minStack = []  //辅助栈，放最小值，
    }
    push(x: number): void {
        this.stack.push(x)   //如果当前最小栈没有元素  或者 要入栈小于等于最小栈栈顶元素
        if (this.minStack.length == 0 ||x <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(x)  //就入栈
        }
    }
    pop(): void {
        let x = this.stack.pop()
        if(x == this.minStack[this.minStack.length-1]){  //检查出栈元素是不是最小栈栈顶元素
            this.minStack.pop()
        }
    }
    top(): number {
        return this.stack[this.stack.length-1]
    }
    getMin(): number {
        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.getMin()
 */

0 赞同 0 条回复

e=mc² 普通 2024年3月9日下午9:31

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() || stack2.peek() >= x) {
            stack2.push(x);
        }
    }

    public void pop() {
        if (!stack1.isEmpty()) {
            //将 Integer 对象转换为原始的 int 类型进行比较，这样就可以确保比较的是值而不是引用
            if (stack1.peek().intValue() == stack2.peek().intValue()) {
                stack2.pop();
            }
            stack1.pop();
        }
    }

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

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

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

0 赞同 0 条回复

helloMoon 普通 2024年3月9日下午7:55

包含min函数的栈java

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

0 赞同 0 条回复

零普通 2024年3月8日下午5:58

思路：用一个栈存储当前栈的最小值
代码：

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> 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);
        }
    }

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

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

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

0 赞同 0 条回复

东普通 2024年3月8日下午4:43

class MinStack {
    Stack<Integer> A;
    Stack<Integer> B;

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

    public void push(int x) {
        //栈A存放所有数据，栈B只存放逐步递减的数据
        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();
    }
}

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

Yeah~ 普通 2024年3月8日下午3:39

class MinStack {
public:
stack st1,st2;
/** initialize your data structure here. */
MinStack() {

}

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

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

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

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

};
//用另一个栈记录最小值，时间O(1)，O(n)

0 赞同 0 条回复

mpweixin用户普通 2024年3月7日下午9:48

java
class MinStack{
Stack 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 getMin(){
return B.peek();
}
}
提交

0 赞同 0 条回复

普通 2024年3月7日下午8:14

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

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

void pop() {
    if(stk1.top()==stk2.top())
        stk2.pop();
    stk1.pop();
}

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

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

};
时间O(1),空间O(n)

0 赞同 0 条回复

墨丘俐普通 2024年3月7日下午5:20

class MinStack {
Stack stack;
Stack minstack;

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

}

public void push(int x) {
    stack.push(x);
    if(minstack.isEmpty()){
        minstack.push(x);

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

        }
    }

}

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


}

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

}

public int getMin() {
    return minstack.peek();

}

}
一个存当前最小，一个正常存

0 赞同 0 条回复

　南木普通 2024年3月7日下午5:15

①双栈，一个存当前最小，一个正常存时间复杂度O（1）空间复杂度O（n）
②单栈遍历，时间复杂度O（n），空间复杂度O（1）

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 getMin() {
        return B.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年3月7日下午2:14

class MinStack {
    // 用两个栈来实现，其中一个栈顶保留所有数据中的最小值
    // 每次元素入栈时，第一个栈正常放入元素，第二个栈判断此时元素与栈顶元素大小关系
    // 出栈时第一个栈正常出栈，第二个栈判断元素与第一个栈栈顶元素的大小相等时才出栈
    // 获取最小值时直接让第二个栈的栈顶元素出栈即可

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

    public MinStack() {
        this.s1 = new Stack<>();
        this.s2 = new Stack<>();
    }

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

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

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

    public int getMin() {
        return s2.peek();
    }
    // 时间复杂度 O(1)
    // 空间复杂度 O(n) 最好情况是第一个入栈的元素是最小元素，最坏情况是每一个入栈的元素是最小元素
}

0 赞同 0 条回复

Let it be 永久会员 2024年3月7日下午1:04

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

}
方法2:
class MinStack {
StackA;
private int min = Integer.MAX_VALUE;
/** initialize your data structure here. */
public MinStack() {
A = new Stack();
}

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

public void pop() {
    if(A.pop().equals(min)){
        min = A.pop();
    }
}

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

public int getMin() {
    return min;
}

}

0 赞同 0 条回复

kfaebot 普通 2024年3月7日上午10:37

class MinStack {
public:
    /** initialize your data structure here. */
    stack main_stack;
    stack help_stack;

    MinStack() {

    }

    void push(int x) {
        main_stack.push(x);
        //若辅助栈为空或者栈顶元素大于压入元素
        if(help_stack.empty()||help_stack.top()>=x){
            help_stack.push(x);
        }
    }

    void pop() {
        //保持有可能被视为最小元素的元素一致性
        if(main_stack.top()==help_stack.top()){
            help_stack.pop();
        }
        main_stack.pop();
    }

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

    int getMin() {
        return help_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 条回复

紫芝普通 2024年3月7日上午8:00

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

type MinStack struct {
    normal, mini []int
}


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


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


func (this *MinStack) Pop()  {
    length := len(this.normal)
    res := this.normal[length-1]
    this.normal = this.normal[:length-1]
    if res == this.mini[len(this.mini)-1] {
        this.mini = this.mini[:len(this.mini)-1]
    }
}


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


func (this *MinStack) GetMin() int {
    return this.mini[len(this.mini)-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.GetMin();
 */

0 赞同 0 条回复

HU 普通 2024年3月7日上午5:56

/**
 * 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);
    // 如果stack2中没有元素，或stack2的栈顶元素的值大于等于x，则将x压入stack2
    if(this.stack2.length == 0 || this.stack2.slice(-1)[0] >= x) {
        this.stack2.push(x);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    // 首先stack1中有元素才出栈（stack1中有元素，stack2中就必有元素）
    if(this.stack1.length != 0) {
        let cur = this.stack1.pop();
        // 如果stack1中出栈元素的值等于stack2中栈顶元素的值，则stack2也出栈
        if(cur == this.stack2.slice(-1)[0]) {
            this.stack2.pop();
        }
        return cur;
    }
};

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

0 赞同 0 条回复

神经蛙普通 2024年3月6日下午11:47

class MinStack {
public:
stackA, B;
/** initialize your data structure here. */
MinStack() {

}

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

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

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

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

};
打卡

0 赞同 0 条回复

南梁陈庆之普通 2024年3月6日下午11:27

定义两个栈，一个栈作为主数据存储，一个存储从小到到大的栈

class MinStack {

    Stack<Integer> stackA , stackB;

    public MinStack() {
        stackA = new Stack<>();
        stackB = new Stack<>();
    }

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

        if (stackB.isEmpty() || stackB.peek() >= x) {
            stackB.add(x);
        }    


    }

    public void pop() {

        if (stackB.peek().equals(stackA.pop())) {
            stackB.pop();
        }
    }

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

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

NULL 普通 2024年3月6日下午9:10

class MinStack {

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

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

}

public void pop() {
    int temp = stackA.pop();
    if(temp == stackB.peek()){
        stackB.pop();
    }
}

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

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

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

0 赞同 0 条回复

Free 普通 2024年3月6日下午8:47

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

    void push(int x) 
    {
        res.push(x);
        if(minsk.empty() || minsk.top() > x)
            minsk.push(x);
        else
            minsk.push(minsk.top());
    }

    void pop() 
    {
        minsk.pop();
        res.pop();
    }

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

    int getMin() 
    {
        return minsk.top();
    }
private:
    stack<int> res;
    stack<int> minsk;
};

/**
 * 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年3月6日下午6:55

class MinStack {

Stack<Integer> main ;
Stack<Integer> sup;

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

}

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

public void pop() {
    if(main.empty())
        return ;
    if( main.peek().equals(sup.peek()))
        sup.pop();
    main.pop();
}

public int top() {
    int top = main.peek();
    return top;
}

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

}
//打卡

0 赞同 0 条回复

Jimmy 普通 2024年3月6日下午5:11

定义两个栈，一个栈用作正常栈，另一个用来存储从小到大排序的栈，时间复杂度O(1)，空间复杂度O(n)

class MinStack {
private:
    stack<int> stack1;
    stack<int> stack2;
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.top() == stack2.top()){
            stack2.pop();
        }
        stack1.pop();
    }

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

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

0 赞同 0 条回复

一个达不刘普通 2024年3月6日下午4:50

栈B的顶部是栈A的最小元素。

stack A,B;
MinStack() {}

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

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

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

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

0 赞同 0 条回复

Jankin 普通 2024年3月6日下午4:41

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().intValue()) {
            minStack.push(val);
        }
    }

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

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

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

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

0 赞同 0 条回复

mpweixin用户普通 2024年3月6日下午1:14

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

public void push(int x) {
    A.add(x);
    if(B.empty()||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();
}

}

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

Thaddeus 永久会员 2024年3月6日上午10:09

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

    }

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

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

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

    int getMin() {
        return st2.top();
    }
private:
    stack<int> st1; // 普通栈
    stack<int> st2; // 单调栈
};

0 赞同 0 条回复

Yuki 永久会员 2024年3月6日上午9:24

打卡
https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/solutions/2670164/zui-xiao-zhan-by-yukislab-bwp0

0 赞同 0 条回复

ChenZhangHangTime 永久会员 2024年3月6日上午9:22

感觉这题比较简单，我感觉比那个链表的题好理解很多，可能原因在于这里没有那么多判断的条件吧，整体代码也比较好理解。
class MinStack {
Stack stack1 = new Stack();
Stack stack2 = new Stack();
/** initialize your data structure here. */
public MinStack() {
this.stack1 =stack1;
this.stack2 = stack2;
}

public void push(int x) {

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

public void pop() {

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

public int top() {

return stack1.peek();
}

public int getMin() {

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

0 赞同 0 条回复

进取普通 2024年3月6日上午9:04

class MinStack {
public:
stack st1, st2;
/** initialize your data structure here. */
MinStack() {

}

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

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

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

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

};打卡，关键在于用一个栈维护降序序列

0 赞同 0 条回复

Yox 普通 2024年3月6日上午3:01

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 getMin(self) -> int:
    return self.B[-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.getMin()

时间O（1）空间O（N）

0 赞同 0 条回复

Raphtalia. 普通 2024年3月6日上午12:37

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

}

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

}

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

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

int getMin() {
    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->getMin();
*/
时间复杂度O（1），空间复杂度O（n）

0 赞同 0 条回复

莫～慢～待普通 2024年3月6日上午12:23

class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode temp1=headA;
ListNode temp2=headB;
while((temp1!=null)||(temp2!=null))
{
if(temp1temp2)
return temp1;
if(temp1null)
temp1=headB;
else
temp1=temp1.next;
if(temp2null)
temp2=headA;
else
temp2=temp2.next;
}
return null;
}
}
时间复杂度：O(1)
额外空间复杂度：O(n)
维护一个从栈顶到栈底的单调递增栈

0 赞同 0 条回复

机电皮怪永久会员 2024年3月5日下午11:49

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

“`C++
class MinStack {
stack minstack,stack1;
public:
/** initialize your data structure here. */
MinStack() {

}

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

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

    stack1.pop();
}

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

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

};

“`

0 赞同 0 条回复

=.= 普通 2024年3月5日下午10:44

class MinStack {

/** initialize your data structure here. */
Deque<Integer> stack1;
Deque<Integer> stack2;

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

public void push(int x) {
    stack1.addLast(x);
    if(stack2.isEmpty()) stack2.addLast(x);
    else{
        int temp = stack2.getLast();
        if(temp < x) stack2.addLast(temp);
        else stack2.addLast(x);
    }
}

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

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

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

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

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月5日下午9:37

class MinStack {
    Stack stack1;
    Stack stack2;

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

    //时间复杂度O（n） 空间o(1)
    public void push(int x) {
        stack1.push(x);
        if(stack2.isEmpty() || stack2.peek() >= x){
            stack2.push(x);
        }

    }

    //时间复杂度O（1） 空间o(1)
    public void pop() {
         if(stack1.peek().intValue() == stack2.peek().intValue()){
            stack2.pop();
        }

        stack1.pop();
    }

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

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

0 赞同 0 条回复

方铎码农普通 2024年3月5日下午9:01

思路很难想到但是并不难实现，主要是开一个辅助的“最小值栈”，只把最小值推进去，只有值比栈顶小才推进去，比栈顶大就不推进去，从而实现了在$O(1)$时间复杂度上完成了提取最小值的过程，代价只是一个栈，额外的$O(n)$的空间复杂度。

class MinStack {

    Deque dataStack;
    Deque minStack;
    /** Integerlize your data structure here. */
    public MinStack() {
        this.dataStack = new ArrayDeque();
        this.minStack = new ArrayDeque();
    }

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

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

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

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

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

需要注意的边界条件是出栈时候，如果要出的是最小值，必须把辅助栈里的最小值一起出了，否则做不到辅助栈栈顶始终是最小值

1 赞同 0 条回复

王位詮釋普通 2024年3月5日下午8:58

class MinStack {
    List<Integer> list;
    int lowest = Integer.MAX_VALUE;//初始值为int的最大值
    /** initialize your data structure here. */
    public MinStack() {
        list = new ArrayList<>();
    }

    public void push(int x) {
        lowest = x<lowest?x:lowest;
        list.add(x);
    }

    public void pop() {
        int index = list.size()-1;
        list.remove(index);
        lowest = Min();
    }

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

    public int getMin() {
        return lowest;
    }

    public int Min(){
        int min = Integer.MAX_VALUE;
        for(int value:list){
            min = value<min?value:min;
        }
        return min;
    }
}
我的思路很简单，因为要在常数复杂度获取最小值，那就维护一个栈中最小值
但是插入时候最小值很容易获得，只需要进行比较，但是pop的时候就得重新获取最小值，这个时间复杂度就得遍历整个栈（我这里用动态数组当栈了）才能获得，时间复杂度O(n)
空间复杂度：O(n)

0 赞同 0 条回复

言之命至普通 2024年3月5日下午8:34

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

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

0 赞同 0 条回复

heathhou 普通 2024年3月5日下午8:24

class MinStack {
public:
    stack stack1;
    stack stack2;
    /** 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()){
            int a = stack1.top();
            stack1.pop();
            if(!stack2.empty() && stack2.top() == a){
                stack2.pop();
            }
        }

    }

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

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

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

0 赞同 0 条回复

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

共以下 45 个回答

Your MinStack object will be instantiated and called as such:

obj = MinStack()

obj.push(x)

obj.pop()

param_3 = obj.top()

param_4 = obj.getMin()

# 回答此问题取消回复

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

共以下 45 个回答

Your MinStack object will be instantiated and called as such:

obj = MinStack()

obj.push(x)

obj.pop()

param_3 = obj.top()

param_4 = obj.getMin()

# 回答此问题 取消回复

# 回答此问题取消回复