请设计一个栈,除了常规栈支持的pop与push函数以外,还支持min函数,该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
时间: 2024-03-27 19:37:42 浏览: 11
好的,我来帮你设计这个栈。我们可以使用两个栈来实现,一个栈用来存储元素,另外一个栈用来存储最小值。具体实现如下:
```python
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, x):
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def pop(self):
if self.stack[-1] == self.min_stack[-1]:
self.min_stack.pop()
self.stack.pop()
def top(self):
return self.stack[-1]
def get_min(self):
return self.min_stack[-1]
```
其中,push() 函数用来将元素压入栈中,如果该元素比当前最小值小,就将该元素压入最小值栈中。pop() 函数用来将栈顶元素弹出,如果栈顶元素是当前最小值,就将最小值栈顶元素弹出。top() 函数用来获取栈顶元素。get_min() 函数用来获取当前栈中的最小值。
以上实现中,push、pop和get_min操作的时间复杂度均为O(1)。