题解 | JZ21 栈的压入、弹出序列

• 头记：这道题不理解他需要做什么？并没有像力扣225.队列实现栈 或者是232.栈实现队列 这样明确说明问题。
• 理解：本题实际上就是通过栈来实现栈，本题关键点是在O(1)空间下，来记录栈中的最小值
• 时间：2021年8月3号

import java.util.Stack;
/***
   头记：这道题确实看不懂他想要做什么？

   理解：实际上可以通过栈来实现栈，本题关键点是在O(1)空间下，来记录栈中的最小值
*/
public class Solution {

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> helper = new Stack<>(); //辅助栈，用来存贮记录栈中已存在的最小值

    public void push(int node) {
        //将node放入stack中，并将最小值更新

        //判断最小值，是否需要更新
//         if (helper == null) { //此处不可以使用helper == null，会出现越界情况，可以使用isEmpty()
//             helper.push(node);
//         } else {
//             if (helper.peek() >= node) {
//                 //如果当前节点大于即将添加的元素node，则更新min();
//                 helper.push(node); 
//             } else {
//                 helper.push(helper.peek());
//             }
//         }
         //判断最小值，是否需要更新
        if (helper.isEmpty() || helper.peek() >= node) { //此处不可以使用helper == null，会出现越界情况，可以使用isEmpty()
            helper.push(node);
        } else {
            //如果当前节点大于即将添加的元素node，则更新min();
            helper.push(helper.peek());
        }

        stack.push(node);
    }

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

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

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