描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：

1. push(value):将value压入栈中
2. pop():弹出栈顶元素
3. top():获取栈顶元素
4. min():获取栈中最小元素

思路1：自定义链表结构

自己实现链表，Node节点中存储min值

public class Solution {
    Node head = null;
    Node tail = null;
    public void push(int node) {
        if(head == null) {
            head = new Node(node);
            head.min = node;
            tail = head;
            return;
        }
        tail.next = new Node(node);
        //每个节点存储当前的最小值
        tail.next.min = Math.min(node, tail.min);
        tail = tail.next;
    }
    
    public void pop() {
        if(head == tail) {
            head = null;
            tail = null;
            return;
        }
        Node tmp = head;
        //也可以实现双链表，便于删除节点
        while(tmp != null) {
            if(tmp.next == tail) {
                tail = tmp;
                tmp.next = null;
                return;
            }
            tmp = tmp.next;
        }
    }
    
    public int top() {
        return tail.val;
    }
    
    public int min() {
        return tail.min;
    }
    
    static class Node {
        int val;
        int min;
        Node next;
        Node(int val) {
            this.val = val;
        }
    }
}

思路2：使用元组存储元素

自定义Entry，栈中每一层同时保存当前值和最小值

public class Solution {
    Stack<Entry> stack = new Stack<>();
    public void push(int node) {
        if(stack.isEmpty()) {
            stack.push(new Entry(node, node));
            return;
        }
        stack.push(new Entry(node, Math.min(node, min())));
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek().val;
    }
    
    public int min() {
        return stack.peek().min;
    }
    
    static class Entry {
        int val;
        int min;
        Entry(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }
}

思路3：辅助栈

栈1保存值，栈2存储当前栈1的最小值，当被推出的数据等于最小值时，栈2也推出。

例如：栈1=[9,10,7,3,3,5]，栈2=[9,7,3,3]

public class Solution {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    
    public void push(int node) {
        stack1.push(node);
        if(stack2.isEmpty() || node <= stack2.peek()) {
            stack2.push(node);
        }
    }
    
    public void pop() {
        int value = stack1.pop();
        if(value == stack2.peek()) {
            stack2.pop();
        }
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        return stack2.peek();
    }
}

思路4：栈中保存最小值

1. push的时候先存入当前的最小值，即该最小值之下的元素都比它大
2. pop的时候一次弹出两个元素，并保存当前栈最小值

例如：

[9] --> 元素3，min=4
[4] --> min
[4] --> 元素2，min=4
[8] --> min
[8] --> 元素1，min=8
[MAX] --> min，没有元素，min=MAX_VALUE

public class Solution {
    Stack<Integer> stack = new Stack<>();
    //栈底为最大值
    int min = Integer.MAX_VALUE;
    public void push(int node) {
        stack.push(min);
        if(node < min) {
            min = node;
        }
        stack.push(node);
    }
    
    public void pop() {
        stack.pop();
        min = stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return min;
    }
}