单调栈入门与实战

单调栈，顾名思义，是指一个栈，其元素具有单调性。具体来说，如果一个栈中的元素满足一定的单调性，例如递增或递减，那么我们就可以利用这个特性来解决一些复杂的问题。

在计算机科学中，单调栈的应用非常广泛。例如，在寻找数组中每个元素的左边或右边第一个比它大的元素时，我们可以使用单调栈来优化算法。再比如，在解决一些涉及排序的问题时，单调栈也可以发挥重要的作用。

下面，我们将通过一个简单的例子来演示单调栈的使用。假设我们有一个数组 arr，我们想要找到每个元素的左边或右边第一个比它大的元素。我们可以使用单调栈来解决这个问题。

首先，我们需要定义一个单调栈。这个栈的特点是，它的元素是递增的。我们可以使用 Python 来实现这个栈：

class MonotonicStack:
    def __init__(self):
        self.stack = []
    def push(self, x):
        while self.stack and self.stack[-1] > x:
            self.stack.pop()
        self.stack.append(x)
    def pop(self):
        return self.stack.pop()

这个栈的实现使用了单调递减的特性。当我们向栈中添加一个新元素时，如果栈顶元素大于新元素，我们就不断地弹出栈顶元素，直到栈顶元素小于或等于新元素为止。这样，我们就可以保证栈中的元素是单调递减的。

接下来，我们可以使用这个单调栈来解决我们的问题。对于数组中的每个元素 arr[i]，我们可以将其与栈顶元素进行比较。如果 arr[i] 大于栈顶元素，那么栈顶元素就是 arr[i] 的右边第一个比它大的元素。如果 arr[i] 小于栈顶元素，那么我们可以将 arr[i] 压入栈中。如果我们遍历完整个数组后，栈中还剩下了元素，那么这些元素就是它们左边第一个比它们大的元素。

下面是一个完整的 Python 代码实现：

def find_next_larger_element(arr):
    stack = MonotonicStack()
    res = [-1] * len(arr)
    for i in range(len(arr)):
        while stack.stack and arr[i] > stack.stack[-1]:
            index = stack.pop()
            res[index] = i
        stack.push(i)
    while stack.stack:
        index = stack.pop()
        res[index] = -1  # 如果栈中剩下的元素没有比它们大的元素，则将它们标记为 -1
    return res

这个函数接受一个数组 arr，并返回一个数组 res，其中 res[i] 表示 arr[i] 的左边或右边第一个比它大的元素的下标。如果 arr[i] 没有比它大的元素，则 res[i] 为 -1。

通过上面的例子，我们可以看到单调栈在解决问题时的优势。使用单调栈可以大大简化算法的复杂度，并提高算法的效率。在实际应用中，我们还可以根据具体问题对单调栈进行优化和改进。