JZ20 包含min函数的栈

1. 最开始每对应一层stack都建立一个辅助的栈存该层的最小值

1 1
3 2
3 2
3 2
2 2
3 3
这样有很多重复的值 优化成
1
3
3
3 1
2 2
3 3
只有当两个栈顶相等时 pop才会弹出辅助的栈

import java.util.Stack;

public class Solution {
    Stack <Integer> stack1 = new Stack <Integer>();
    Stack <Integer> stack2 = new Stack <Integer>();

    public void push(int node) {
        stack1.push(node);
        if(stack2.empty()){stack2.push(node);}
        else if(node < stack2.peek()){stack2.push(node);}
        else {stack2.push(stack2.peek());}
    }

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

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

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

优化版本

import java.util.Stack;

public class Solution {
    Stack <Integer> stack1 = new Stack <Integer>();
    Stack <Integer> stack2 = new Stack <Integer>();

    public void push(int node) {
        stack1.push(node);
        if(stack2.empty() || stack2.peek() >= node){stack2.push(node);}
    }

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

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

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