请设计一个栈,除了常规栈支持的pop与push函数以外,还支持min函数,该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
时间: 2024-03-27 09:37:15 浏览: 39
可以设计一个辅助栈来实现该功能,具体思路如下:
1. 主栈用于存储数据元素,辅助栈用于存储当前最小值。
2. push操作时,将元素压入主栈,并判断该元素是否小于等于辅助栈的栈顶元素,如果是,则将该元素也压入辅助栈。
3. pop操作时,从主栈中弹出栈顶元素,如果该元素等于辅助栈的栈顶元素,则也从辅助栈中弹出该元素。
4. min操作时,直接返回辅助栈的栈顶元素即可。
该栈的时间复杂度为O(1),因为push、pop和min操作都只涉及到栈的入栈、出栈和查找栈顶元素等基本操作,不需要遍历整个栈。具体代码如下:
```python
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def pop(self) -> None:
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
```
注意,在pop操作时,需要比较弹出的元素和辅助栈的栈顶元素是否相等,因为一个元素可能会被压入多次,需要在辅助栈中相应地弹出。
阅读全文