单调栈python
时间: 2023-06-29 20:16:47 浏览: 63
单调栈是一种常见的数据结构,在解决一些特定问题时非常有用。它可以用来求解一些范围内的最大值、最小值、最长连续递增子序列等问题。下面是一个简单的 Python 实现:
```
class MonotonicStack:
def __init__(self):
self.stack = []
def push(self, val):
while self.stack and self.stack[-1] < val:
self.stack.pop()
self.stack.append(val)
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1]
def is_empty(self):
return len(self.stack) == 0
```
这个单调栈实现了四个基本操作:
- push(val):将元素 val 压入栈中。在压入之前,如果栈顶元素比 val 小,则弹出栈顶元素,直到栈顶元素比 val 大或栈为空,然后将 val 压入栈中。
- pop():弹出栈顶元素。
- top():返回栈顶元素。
- is_empty():判断栈是否为空。
使用单调栈的时候,需要根据具体问题来实现 push 操作。下面是一个例子,求解一个数组中每个元素右边第一个比它大的数:
```
def next_larger(nums):
n = len(nums)
res = [-1] * n
stack = MonotonicStack()
for i in range(n):
while not stack.is_empty() and nums[stack.top()] < nums[i]:
res[stack.top()] = nums[i]
stack.pop()
stack.push(i)
return res
```
在这个例子中,我们维护了一个单调递减的栈,每次遇到一个比栈顶元素大的数,就将栈顶元素弹出,并将栈顶元素的答案设为当前数。这样,最后栈中剩下的元素都没有右边比它们大的数,它们的答案就是 -1。时间复杂度为 O(n)。