最小栈

目标

实现支持 getMin() 的栈：

• MinStack() 初始化
• void push(int val) 压栈
• void pop() 出栈
• int top() 取栈顶
• int getMin() 取当前最小值（均需 O(1)）

思路

• 使用 辅助栈 min 或 辅助数组 min[]，在每次 push 时同步记录“当前最小值”。
• 具体策略：
• 若 val <= 当前最小值，把 val 压入 min；
• 否则把 min 的栈顶（当前最小值）再压一份（冗余存储，换取 O(1) getMin）。
• pop() 时两栈（或两数组）同步弹/回退一位。

双栈版实现（冗余最小）

import java.util.Stack;

public class Code_08 {

    // 双栈：data 保存数据；min 保存对应位置的当前最小值
    class MinStack1 {
        public Stack<Integer> data;
        public Stack<Integer> min;

        public MinStack1() {
            data = new Stack<>();
            min = new Stack<>();
        }

        public void push(int val) {
            data.push(val);
            if (min.isEmpty() || val <= min.peek()) {
                min.push(val);
            } else {
                min.push(min.peek());
            }
        }

        public void pop() {
            if (data.isEmpty()) {
                throw new RuntimeException("Stack is empty");
            }
            data.pop();
            min.pop();
        }

        public int top() {
            if (data.isEmpty()) {
                throw new RuntimeException("Stack is empty");
            }
            return data.peek();
        }

        public int getMin() {
            if (min.isEmpty()) {
                throw new RuntimeException("Stack is empty");
            }
            return min.peek();
        }
    }
}
    

数组实现（固定容量）

原理：0~i范围上，相邻位置较大的数滚下去，最大值最终来到i位置，然后0~i-1范围上继续

public class Code_08 {

    // 固定容量版本（示例为 8001，可按需调大）
    class MinStack2 {
        public final int MAXN = 8001;
        public int[] data;
        public int[] min;
        int size;

        public MinStack2() {
            data = new int[MAXN];
            min = new int[MAXN];
            size = 0;
        }

        public void push(int val) {
            if (size >= MAXN) {
                throw new RuntimeException("Stack overflow");
            }
            data[size] = val;
            if (size == 0 || val <= min[size - 1]) {
                min[size] = val;
            } else {
                min[size] = min[size - 1];
            }
            size++;
        }

        public void pop() {
            if (size == 0) {
                throw new RuntimeException("Stack is empty");
            }
            size--;
        }

        public int top() {
            if (size == 0) {
                throw new RuntimeException("Stack is empty");
            }
            return data[size - 1];
        }

        public int getMin() {
            if (size == 0) {
                throw new RuntimeException("Stack is empty");
            }
            return min[size - 1];
        }
    }
}