实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。
时间: 2024-10-09 20:05:05 浏览: 47
实现这样的特殊栈,我们通常会采用一种数据结构,比如维护两个指针:一个普通指针指向栈顶元素,另一个叫做“最小值指针”,它总是指向当前栈中的最小元素。每当元素入栈时,我们首先将其添加到普通栈中,然后比较新元素和当前最小值,如果新元素更小,则更新最小值指针。出栈操作时,先出普通栈顶元素,然后检查是否需要调整最小值指针。
以下是这个特殊栈的一个基本Python实现:
```python
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
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:
top_element = self.stack.pop()
if top_element == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1] if self.stack else None
def get_min(self) -> int:
return self.min_stack[-1] if self.min_stack else None
```
在这个实现中,`push`、`pop`和`top`操作的时间复杂度都是O(1),而`get_min`操作也只需要O(1)时间,因为最小值始终存储在单独的`min_stack`中。
阅读全文