题目描述和要求
设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类：
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素 val 推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
示例解释
示例 1：
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
解题思路
我们可以设计一个辅助栈来存储当前栈中的最小元素。在每次 push 操作时，将当前元素与辅助栈的栈顶元素比较，将较小的元素入栈。这样，在 getMin 操作时，只需要返回辅助栈的栈顶元素即可。
算法实现
import java.util.Stack; public class MinStack { Stack<Integer> stack; Stack<Integer> minStack; public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int val) { stack.push(val); if (minStack.isEmpty() || val <= minStack.peek()) { minStack.push(val); } } public void pop() { if (stack.peek().equals(minStack.peek())) { minStack.pop(); } stack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }
复杂度分析
- 时间复杂度：对于每个操作，时间复杂度都是 O(1)。
- 空间复杂度：额外使用了两个辅助栈，空间复杂度为 O(n)，其中 n 为元素数量。
测试和验证
编写测试用例对算法进行验证，确保其正确性和健壮性。
public class Main { public static void main(String[] args) { MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); System.out.println(minStack.getMin()); // -3 minStack.pop(); System.out.println(minStack.top()); // 0 System.out.println(minStack.getMin()); // -2 } }
总结和拓展
本题通过设计一个辅助栈来实现在常数时间内检索到最小元素的要求，实现了一个最小栈的数据结构。这个算法思路清晰简单，在处理类似问题时是一个不错的选择。
除了当前算法，我们也可以考虑其他实现方式，例如使用双端队列、优先队列等方法来解决类似问题。
参考资料
- 《力扣经典150题》
- LeetCode 官方网站
