image-20210904103317969.png

    这个题大体上和实现了一个栈没有什么区别，而且还不用考虑栈为空的情况。我们需要维护一个变量来记录栈的最小值。

    开始的想法：最开始我想，只要在MinStack中维护一个成员变量min就行了吧，只要每次push元素的时候都进行比较更新不就行了，实现到pop()操作的时候，我突然意识到这样并不行，如果栈顶元素刚好是最小元素，那么当我把栈顶元素删除后，此时栈的最小元素就不得而知了。所以说只全局维护一个变量是不行的。

    改进的思路：由于只维护当前栈的最小元素是不行的，那么我们就要像动态规划那样，储存栈每个状态的最小值，当前栈的最小值可以由上一个状态得到，递推式为dp[i] = min(dp[i-1], val)，这样我们就解决了上面所出现的问题，不会因为删除最小元素后，不知道删除后栈的最小元素了。

    具体实现方案：我们可以在MinStack中维护一个list来保存最小栈每个状态下的最小值。然而我们可以用另外一种更为巧妙的方法来实现，我们在用于构建栈的Node节点中，添加一个属性curStackMin的属性，这样同样可以达到上述的效果，使用Node来保存最小值的信息。

    1. class MinStack {
    2.     private Node head;
    3.     /** initialize your data structure here. */
    4.     public MinStack() {}
    6.     public void push(int val) {
    7.         if(head == null){
    8.             head = new Node(val, val);
    9.         }else{
    10.             head = new Node(val, Math.min(head.curStackMin, val), head);
    11.         }
    12.     }
    14.     public void pop() {
    15.         head = head.next;
    16.     }
    18.     public int top() {
    19.         return head.val;
    20.     }
    22.     public int getMin() {
    23.         //本题不用考虑空栈情况
    24.         //if(head == null){}
    25.         return head.curStackMin;
    26.     }
    28.     private class Node{
    29.         int val;
    30.         //用于保存，该结点加入后，此时栈的最小值
    31.         int curStackMin;
    32.         Node next;
    34.         private Node(){
    35.         }
    36.         private Node(int val, int curStackMin){
    37.             this.val = val;
    38.             this.curStackMin = curStackMin;
    39.         }
    40.         private Node(int val, int curStackMin, Node next){
    41.             this.val = val;
    42.             this.curStackMin = curStackMin;
    43.             this.next = next;
    44.         }
    46.     }
    47. }