最小栈设计并实现一个minstack类pta
时间: 2024-10-10 22:16:28 浏览: 31
最小栈的设计目的是为了在操作元素的同时,能够快速获取当前栈内的最小值。它通常通过维护两个栈来实现:一个普通栈用于存储所有元素,另一个辅助栈专门用于存储最小值。当新元素入栈时,先将其与当前最小值比较,如果小于或等于当前最小值,则同时将该元素压入最小值栈;反之,只将元素压入普通栈。
下面是使用Python实现`MinStack`的一个简单版本:
```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.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def get_min(self) -> int:
return self.min_stack[-1] if self.min_stack else None
```
在这个类中:
- `push()`方法在添加元素到主栈的同时,检查是否需要更新最小值栈。
- `pop()`方法除了删除主栈顶元素外,还会检查是否有需要从最小值栈移除的情况。
- `top()`返回主栈顶部元素。
- `get_min()`直接返回最小值栈的顶部元素,即当前栈中的最小值。
阅读全文