【LeetCode每日打卡】155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

Constraints:

Methods pop, top and getMin operations will always be called on non-empty stacks.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

两个栈一个普通栈，一个用来存储最小值。
class MinStack {
private Stack<integer> minStack;
private Stack<integer> stack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
minStack = new Stack();
}</integer></integer>

public void push(int x) {
    stack.push(x);
    if(!minStack.isEmpty()){
        int top = minStack.peek();
        if(x<top){
            minStack.push(x);
        }else{
            minStack.push(top);
        }
    }else{
        minStack.push(x);
    }
}

public void pop() {
    minStack.pop();
    stack.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(x);
obj.pop();
int param_3 = obj.top();
int param_4 = obj.getMin();
/
开始优化对最小栈进行优化
注意判断两个栈时不能用 == 因为是 Integer 要用equals
if(minStack.peek().equals(stack.peek())){

改动 push方法

if(x<=top){
minStack.push(x);
}

pop方法

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

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

public void push(int x) {
    stack.push(x);
    if(!minStack.isEmpty()){
        int top = minStack.peek();
        if(x<=top){
            minStack.push(x);
        }
    }else{
        minStack.push(x);
    }
}

public void pop() {
    if(minStack.peek().equals(stack.peek())){
         minStack.pop();
    }
    stack.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(x);
obj.pop();
int param_3 = obj.top();
int param_4 = obj.getMin();
/

方法三两个栈合成一个栈
遇到需要更新最小值的时候就把上一个最小值也压进去，当最小值需要更新时，再弹出来的就是上一次最小值

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

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

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

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

public int getMin() {
    return minStack;
}

}

/**

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();
/
方法四
差值存储

想不到评论区各种大神出没

每次存储当前值和最小值的差值，如果当前值和最小值的差值是负数了，说明需要更换最小值了。

public class MinStack {
long min;
Stack<long> stack;</long>

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

public void push(int x) {
    if (stack.isEmpty()) {
        min = x;
        stack.push(x - min);
    } else {
        stack.push(x - min);
        if (x < min){
            min = x; // 更新最小值
        }

    }
}

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

    long pop = stack.pop();

    //弹出的是负值，要更新 min
    if (pop < 0) {
        min = min - pop;
    }

}

public int top() {
    long top = stack.peek();
    //负数的话，出栈的值保存在 min 中
    if (top < 0) {
        return (int) (min);
    //出栈元素加上最小值即可
    } else {
        return (int) (top + min);
    }
}

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

}

作者：windliang
链接：https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法五
存成一个节点包含两个信息其实和两个栈的方法一思想一样，代码实现更加简单不会出错

class MinStack {
class Node{
int value;
int min;
Node next;

    Node(int x, int min){
        this.value=x;
        this.min=min;
        next = null;
    }
}
Node head;
//每次加入的节点放到头部
public void push(int x) {
    if(null==head){
        head = new Node(x,x);
    }else{
        //当前值和之前头结点的最小值较小的做为当前的 min
        Node n = new Node(x, Math.min(x,head.min));
        n.next=head;
        head=n;
    }
}

public void pop() {
    if(head!=null)
        head =head.next;
}

public int top() {
    if(head!=null)
        return head.value;
    return -1;
}

public int getMin() {
    if(null!=head)
        return head.min;
    return -1;
}

}