Leetcode Hot100 61-65

法一：使用辅助栈

一个栈正常存，另一个存最小值

class MinStack {Deque<Integer>stack;Deque<Integer>minstack;public MinStack() {stack = new LinkedList<>();minstack = new LinkedList<>();}public void push(int val) {stack.push(val);if(minstack.isEmpty()||val <= minstack.peek()){minstack.push(val);}}public void pop() {Integer pop = stack.pop();if(pop.equals(minstack.peek())){minstack.pop();}}public int top() {return stack.peek();}public int getMin() {return minstack.peek();}
}

法二：创建新的Node节点，Node节点包括val和min

class MinStack {private  static class Node{int value;int min;Node next;Node(int x,int min){this.value = x;this.min = min;next = null;}}private Deque<Node>stack;public MinStack() {stack  = new LinkedList<>();}public void push(int val) {if(stack.isEmpty()){stack.push(new Node(val,val));}else{stack.push(new Node(val,Math.min(stack.peek().min,val)));}}public void pop() {stack.pop();}public int top() {return stack.peek().value;}public int getMin() {return stack.peek().min;}
}

自己实现栈，可以用单链表的头插法

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{//当前值和之前头结点的最小值较小的做为当前的 minNode 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;}
}作者：windliang
链接：https://leetcode.cn/problems/min-stack/solutions/42521/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。