Salesforce Maximal Rectangle：逐行柱状图与单调栈

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版输入为矩形 '0'/'1' 字符矩阵，返回全 1 轴对齐矩形的最大面积；空矩阵和零列返回 0。
• 只求面积，不要求位置；若输入包含非二值或行长不一，代码抛错，这是训练接口约定。
• 矩形长宽可以不同，因此不能直接套 Maximal Square 的三邻居 DP。

解题路线

1. 每行作为矩形底边，heights[c] 记录该列向上连续 '1' 的数量；遇 '0' 就归零。任何以该行为底边的全 1 矩形都对应这个高度数组中的一个柱状图矩形。
2. 对 heights 用非递减高度的下标栈。当前高度低于或等于栈顶时弹出 top；此刻右边第一个更低位置为当前列，左边第一个更低位置为弹出后的栈顶（不存在则 -1），可得宽度 current-left-1，面积为 heights[top]×宽度。
3. 在行尾加高度 0 的哨兵，确保剩余柱子全部出栈。每个下标在一行至多进出栈一次；逐行更新全局最大面积。等高柱统一按 >= 弹出，保证边界处理一致。

手动走一遍

两行 [[1,0,1,1],[1,1,1,1]]：第二行 heights=[2,1,2,2]。后两列形成高 2、宽 2 的矩形，面积 4；四列整体高至少 1，面积也为 4。扫描到行尾哨兵时，会弹出未处理的高度并算出这两个候选。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def maximal_rectangle_area(matrix: list[list[str]]) -> int:
    """Area of the largest all-'1' axis-aligned rectangle."""
    if not matrix:
        return 0
    cols = len(matrix[0])
    if any(len(row) != cols for row in matrix):
        raise ValueError("matrix must be rectangular")
    heights = [0] * cols
    best = 0
    for row in matrix:
        for col, value in enumerate(row):
            if value == "1":
                heights[col] += 1
            elif value == "0":
                heights[col] = 0
            else:
                raise ValueError("matrix values must be '0' or '1'")
        stack: list[int] = []
        for col in range(cols + 1):
            height = heights[col] if col < cols else 0
            while stack and heights[stack[-1]] >= height:
                top = stack.pop()
                left = stack[-1] if stack else -1
                best = max(best, heights[top] * (col - left - 1))
            stack.append(col)
    return best

复杂度

R 行、C 列。高度更新 O(RC)，每行每根柱最多压入与弹出一次，整体时间 O(RC)；heights 和栈各最多 C 项，辅助空间 O(C)。

易错点与追问

容易失分的边界

• 高度遇 0 不归零，会把跨过空格的不合法竖向区域算入。
• 弹出时把宽度误写成 current-top，而非 current-leftBoundary-1；top 不一定是左边界。
• 不加哨兵且忘记清空栈，漏算延伸到行尾的最大矩形。
• 用 Maximal Square 的状态转移求矩形，会漏掉细长但面积更大的答案。

继续深挖

• 若要返回一个最大矩形的位置，在更新 best 时记录底行、弹出高度和左右边界；同面积如何选先定规则。
• 若逐行接收矩阵流，可只保留 heights 与当前行栈，仍是 O(C) 内存。
• 若要统计所有全 1 子矩形数量，单调栈仍可用，但累加逻辑与最大面积不同，不能直接复用 best 更新。