一、题目描述
设计一个支持 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.
提示:
-2^31 <= val <= 2^31 - 1
pop
、top
和getMin
操作总是在 非空栈 上调用push
,pop
,top
, andgetMin
最多被调用3 * 10^4
次
二、解题思路
为了设计一个能在常数时间内检索到最小元素的栈,我们需要在每次 push 操作时记录当前的最小值。这样,在 getMin 操作时,我们就可以直接返回当前的最小值,而不需要进行遍历。
具体来说,我们可以使用一个辅助栈来存储每次 push 操作时的最小值。这样,主栈和辅助栈的大小始终保持一致,且辅助栈的栈顶元素始终表示当前的最小值。
以下是具体的步骤:
- 初始化两个栈:dataStack 和 minStack。dataStack 用于存储所有元素,而 minStack 用于存储每个元素入栈时的最小值。
- 在 push 操作时,首先将元素 val 推入 dataStack。然后,如果 minStack 为空或者 val 小于等于 minStack 的栈顶元素,我们将 val 也推入 minStack。
- 在 pop 操作时,从 dataStack 中弹出栈顶元素。如果这个元素等于 minStack 的栈顶元素,也从 minStack 中弹出栈顶元素。
- 在 top 操作时,返回 dataStack 的栈顶元素。
- 在 getMin 操作时,返回 minStack 的栈顶元素。
三、具体代码
class MinStack {
private Stack<Integer> dataStack;
private Stack<Integer> minStack;
public MinStack() {
dataStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
dataStack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
if (dataStack.pop().equals(minStack.peek())) {
minStack.pop();
}
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- push 操作:O(1)。因为每次 push 只涉及到栈的 push 操作,而栈的 push 操作是常数时间的。
- pop 操作:O(1)。同样,栈的 pop 操作也是常数时间的。
- top 操作:O(1)。栈的 peek 操作是常数时间的。
- getMin 操作:O(1)。由于 minStack 的栈顶始终保持着当前栈的最小值,因此直接返回栈顶元素是常数时间的。
2. 空间复杂度
- 数据栈 dataStack 和 辅助栈 minStack 的空间复杂度都是 O(n),其中 n 是栈中元素的数量。在最坏的情况下,两个栈的大小会相同,因此总的空间复杂度是 O(n)。
综上所述,MinStack 类的每个操作的时间复杂度都是 O(1),而空间复杂度是 O(n)。
五、总结知识点
栈(Stack)的使用:Java 中的
Stack
类是Vector
的一个子类,用于实现后进先出(LIFO)的数据结构。代码中使用了两个Stack
对象,一个用于存储所有元素(dataStack
),另一个用于存储最小元素(minStack
)。类的定义:代码定义了一个名为
MinStack
的类,该类包含两个私有成员变量和四个公共方法。构造函数:
MinStack
类的构造函数MinStack()
用于初始化两个栈。封装:通过将
dataStack
和minStack
声明为私有,实现了封装,使得这些变量只能在类内部被访问和修改。条件语句:
if
语句用于在push
和pop
方法中做条件判断,以决定是否需要向minStack
中添加或移除元素。栈操作:
push
、pop
和peek
是栈的基本操作,分别用于向栈中添加元素、从栈中移除元素和查看栈顶元素。数据结构设计:通过设计一个辅助栈
minStack
来跟踪最小元素,这是一种常见的技巧,用于优化特定问题的解决方案。异常处理:虽然代码中没有显式的异常处理,但是在使用栈时需要注意空栈操作可能会导致
NoSuchElementException
。接口与实现:
MinStack
类定义了一个接口(API),其中包括push
、pop
、top
和getMin
方法,这些都是该类对外提供的服务。类型匹配与比较:在
pop
方法中使用了equals
方法来比较两个Integer
对象的值,这是因为在 Java 中,==
用于比较对象的引用而不是值。
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。