最大矩形面积问题marscode

最大矩形面积问题是经典的计算机科学问题，它通常涉及给定一个非降序的一维数组（比如宽度优先的像素矩阵），目标是找到能够形成的最大矩形，其高度由数组元素构成，而宽度为1。这个问题可以使用栈数据结构来解决。

基本思路是：
1. 初始化两个变量：当前高度`height`和最大矩形面积`maxArea`，并假设第一个元素作为当前矩形的底部。
2. 遍历数组，对于每个元素，如果它的值大于`height`，则将`height`更新为该元素，然后计算新的矩形面积（即`height * (index - top)`），并将这个新面积与`maxArea`比较，取较大者。
3. 如果元素值小于等于`height`，说明当前矩形无法继续增高，此时`top`指向下一个小于或等于`height`的元素的索引，`height`保持不变。
4. 当遍历结束时，`maxArea`就是最大的矩形面积。

以下是使用Python的伪代码描述：

def maxRectangle(heights):
    heights.append(float('-inf')) # 添加边界条件
    stack = [-1] # 栈，top指向上一个比当前小的元素
    max_area = 0
    for i in range(len(heights)):
        while stack and heights[i] <= heights[stack[-1]]:
            h = heights[stack.pop()]
            w = i - stack[-1] - 1 if stack else i
            max_area = max(max_area, h * w)
        stack.append(i) # 更新栈顶
    return max_area

# 示例
heights = [2, 1, 5, 6, 2, 3]
print(maxRectangle(heights))  # 输出：10