Python中单调栈的函数

在Python中，单调栈是一种常用的数据结构，用于解决一些与数组或列表相关的问题。单调栈的特点是栈内元素保持单调递增或单调递减的顺序。

下面是一个示例函数，用于实现单调栈的功能：

def monotonic_stack(arr):
    stack = []  # 创建一个空栈
    result = []  # 用于存储结果的列表

    for i in range(len(arr)):
        while stack and arr[i] < stack[-1]:
            stack.pop()  # 弹出栈顶元素，直到栈为空或者当前元素大于等于栈顶元素
        stack.append(arr[i])  # 将当前元素入栈

    while stack:
        result.append(stack.pop())  # 将栈中剩余的元素依次弹出并存入结果列表

    return result

这个函数接受一个数组作为输入，并返回一个新的数组，其中的元素是原始数组中每个元素右边第一个比它小的元素。

例如，对于输入数组 `[3, 4, 2, 7, 5, 8, 1]`，函数将返回 `[2, 2, 1, 5, 1, 1, -1]`。

这个函数的实现基于单调递减栈的思想。它遍历输入数组，如果当前元素小于栈顶元素，则将栈顶元素弹出，直到栈为空或者当前元素大于等于栈顶元素。然后将当前元素入栈。最后，将栈中剩余的元素依次弹出并存入结果列表。

这样，我们就可以利用单调栈来解决一些与数组相关的问题，例如找到下一个更大/更小的元素、计算柱状图中最大的矩形等。