单调栈给定长的的最大矩形

单调栈可以用来解决给定一个直方图，求最大的矩形面积。具体步骤如下：

1. 定义一个栈，存储直方图中每个柱子的下标。

2. 从左到右遍历直方图，对于每个柱子，将其下标入栈。

3. 如果当前柱子的高度小于等于栈顶柱子的高度，说明当前柱子不能向右扩展，以栈顶柱子为高的最大矩形已经确定，计算其面积，并将栈顶柱子出栈。

4. 如果当前柱子的高度大于栈顶柱子的高度，说明当前柱子可以向右扩展，将当前柱子的下标入栈。

5. 当遍历完整个直方图后，栈中剩余的柱子都是可以向右扩展的，以它们为高的最大矩形需要单独计算。

6. 在计算过程中，可以用一个数组记录每个柱子的左右边界下标，用于计算矩形的宽度。

下面是具体的代码实现（假设直方图存储在数组 heights 中）：

def largestRectangleArea(heights):
    stack = []
    n = len(heights)
    left = [0] * n
    right = [n] * n
    for i in range(n):
        while stack and heights[i] <= heights[stack[-1]]:
            stack.pop()
        if stack:
            left[i] = stack[-1] + 1
        stack.append(i)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[i] <= heights[stack[-1]]:
            stack.pop()
        if stack:
            right[i] = stack[-1]
        stack.append(i)
    ans = 0
    for i in range(n):
        ans = max(ans, (right[i] - left[i]) * heights[i])
    return ans

时间复杂度为 O(n)，空间复杂度为 O(n)。