普通方法（辅助栈）：需要另外一个栈 用来存放每一时刻的min值
import java.util.Stack; public class MinStack { // 数据栈 private Stack<Integer> data; // 辅助栈 private Stack<Integer> helper; /** * initialize your data structure here. */ public MinStack() { data = new Stack<>(); helper = new Stack<>(); } // 思路 2：辅助栈和数据栈不同步 // 关键 1：辅助栈的元素空的时候，必须放入新进来的数 // 关键 2：新来的数小于或者等于辅助栈栈顶元素的时候，才放入（特别注意这里等于要考虑进去） // 关键 3：出栈的时候，辅助栈的栈顶元素等于数据栈的栈顶元素，才出栈，即"出栈保持同步"就可以了 public void push(int x) { // 辅助栈在必要的时候才增加 data.add(x); // 关键 1 和 关键 2 if (helper.isEmpty() || helper.peek() >= x) { helper.add(x); } } public void pop() { // 关键 3：data 一定得 pop() if (!data.isEmpty()) { // 注意：声明成 int 类型，这里完成了自动拆箱，从 Integer 转成了 int，因此下面的比较可以使用 "==" 运算符 // 如果把 top 变量声明成 Integer 类型，下面的比较就得使用 equals 方法 int top = data.pop(); if(top == helper.peek()){ helper.pop(); } } } public int top() { if(!data.isEmpty()){ return data.peek(); } throw new RuntimeException("栈中元素为空，此操作非法"); } public int getMin() { if(!helper.isEmpty()){ return helper.peek(); } throw new RuntimeException("栈中元素为空，此操作非法"); } }巧妙版：只需要一个stack，stack中存的是与min的差值 但由于min是两个整数之间的差值，有可能会出现差值超过整数边界值的情况，因此要变成Long型
import java.util.Stack; class MinStack { Stack<Long> stack; long min; /** initialize your data structure here. */ public MinStack() { stack = new Stack<>(); } public void push(int x) { if(stack.isEmpty()){ stack.push(0L); min = x; }else { stack.push(x - min); if (x < min) { min = x; } } } public void pop() { if(stack.isEmpty()){ return; } Long temp = stack.pop(); if(temp<0){ min = min - temp; } } public int top() { Long top = stack.peek(); if (top > 0) { return (int)(stack.peek()+min); } return (int)min; } public int getMin() { return (int)min; } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */