思路:
除了最后一个获取最小值以外,其他都可以使用一个栈来实现,但是如果当前一个最小值被移除了,如果获取第二小的值,这个是需要记录的。所以最好的办法是两个栈。一个作为主栈存放数据,一个作为辅栈,存放最小值。代码如下:
class MinStack {
// 主栈,用于存储所有的元素。
Stack<Integer> stack;
// 辅助栈,用于存储每个状态下的最小值。
Stack<Integer> minStack;
// 构造函数初始化两个栈。
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
// push 方法,将元素 val 推入栈中。
public void push(int val) {
// 元素推入主栈。
stack.push(val);
// 判断辅助栈是否为空,若为空直接将 val 推入辅助栈。
// 否则将 val 与辅助栈顶元素比较,推入较小值。
// 这样可以保证辅助栈的栈顶始终是当前所有元素的最小值。
if (minStack.isEmpty()) {
minStack.push(val);
} else {
minStack.push(Math.min(minStack.peek(), val));
}
}
// pop 方法,从栈中移除顶部元素。
public void pop() {
// 同时从主栈和辅助栈中移除栈顶元素。
// 保持两个栈的同步,确保辅助栈顶元素正确反映当前最小值。
stack.pop();
minStack.pop();
}
// top 方法,获取栈顶元素,即最后一个推入主栈的元素。
public int top() {
return stack.peek();
}
// getMin 方法,返回当前栈中的最小元素。
// 直接返回辅助栈的栈顶元素,因为它存储的是当前的最小值。
public int getMin() {
return minStack.peek();
}
}