1、最小栈

力扣

辅助栈

引入一个辅助栈，专门存储最小值，与主栈同步进出 需要注意辅助栈的进栈规则

  1.     Deque<Integer> xStack;
  2.     Deque<Integer> minStack;
  5.     public MinStack() {
  6.         xStack = new LinkedList<Integer>();
  7.         minStack = new LinkedList<Integer>();
  8.         minStack.push(Integer.MAX_VALUE);
  9.     }
  11.     public void push(int x) {
  12.         xStack.push(x);
  13.         minStack.push(Math.min(minStack.peek(), x)); //取最小值，当
  14.     }
  16.     public void pop() {
  17.         xStack.pop();
  18.         minStack.pop();// 只会存储最小值，所以可以出栈
  19.     }
  21.     public int top() {
  22.         return xStack.peek();
  23.     }
  25.     public int getMin() {
  26.         return minStack.peek();
  27.     }

双插法

与辅助栈类似，同时存储当前元素和当前的最小值，出栈时出两次，获得最小值时获取当前的倒数第二个数字

  1.     Stack<Integer> stack = new Stack<Integer>();
  2.     public void push(int x) {
  3.         if(stack.isEmpty()){
  4.             stack.push(x);
  5.             stack.push(x);
  6.         }else{
  7.             int tmp = stack.peek();
  8.             stack.push(x);
  9.             if(tmp<x){
  10.                 stack.push(tmp);
  11.             }else{
  12.                 stack.push(x);
  13.             }
  14.         }
  15.     }
  16.     public void pop() {
  17.         stack.pop();
  18.         stack.pop();
  19.     }
  21.     public int top() {
  22.         return stack.get(stack.size()-2);
  23.     }
  25.     public int getMin() {
  26.         return stack.peek();
  27.     }

适用链表实现

上述两种方式都是使用Java自带的数据结构，还可以自定义数据结构

  1. class MinStack {
  2.     private Node head; // 定义栈顶元素节点
  4.     // 元素入栈操作
  5.     public void push(int x) {
  6.         // 如果栈为空，则将新元素作为栈顶元素
  7.         if (head == null) {
  8.             head = new Node(x, x);
  9.         } else {
  10.             // 如果栈不为空，则将新元素作为新的栈顶元素，并更新最小值
  11.             head = new Node(x, Math.min(x, head.min), head);
  12.         }
  13.     }
  15.     // 元素出栈操作
  16.     public void pop() {
  17.         head = head.next; // 将栈顶元素指向下一个节点，实现出栈操作
  18.     }
  20.     // 获取栈顶元素的值
  21.     public int top() {
  22.         return head.val;
  23.     }
  25.     // 获取栈中的最小值
  26.     public int getMin() {
  27.         return head.min;
  28.     }
  30.     // 定义链表节点类
  31.     private class Node {
  32.         int val; // 节点的值
  33.         int min; // 节点前缀的最小值
  34.         Node next; // 节点的后继节点
  36.         // 构造函数
  37.         private Node(int val, int min) {
  38.             this(val, min, null);
  39.         }
  41.         private Node(int val, int min, Node next) {
  42.             this.val = val;
  43.             this.min = min;
  44.             this.next = next;
  45.         }
  46.     }
  47. }

head 是该栈的栈顶元素，它的作用是指向栈顶元素的节点。在进行元素的入栈和出栈操作时，会改变 head 所指向的节点，从而实现对栈的修改。