85. [✔][H]最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = [["0"]]
输出：0

示例 4：

输入：matrix = [["1"]]
输出：1

示例 5：

输入：matrix = [["0","0"]]
输出：0

提示：

• rows == matrix.length
• cols == matrix[0].length
• 1 <= row, cols <= 200
• matrix[i][j] 为 '0' 或 '1'

---

题解：

详细通俗的思路分析，多解法

// @lc code=start
function maximalRectangle(matrix: string[][]): number {
    let m = matrix.length;
    let n = matrix[0].length;

    const largestRectangleArea = (heights: number[]) => {
        let newHeights = [0, ...heights, 0];
        let max = 0;
        let stack: number[] = [];

        for (let i = 0; i < newHeights.length; i++) {
            while (stack.length > 0 && newHeights[i] < newHeights[stack[stack.length - 1]]) {
                let curIndex = stack.pop()!;
                let curHeight = newHeights[curIndex];

                let leftIndex = stack[stack.length - 1];
                let rightIndex = i;

                let width = (rightIndex - leftIndex + 1) - 2;

                max = Math.max(max, width * curHeight);
            }
            stack.push(i);
        }
        return max;
    }

    let heights = new Array(n).fill(0);
    let max = 0;

    for (let row = 0; row < m; row++) {
        for (let col = 0; col < n; col++) {
            if (matrix[row][col] === "1") {
                heights[col] += 1;
            } else {
                heights[col] = 0
            }
        }
        // 最巧妙的是调用84题的逻辑
        max = Math.max(max, largestRectangleArea(heights));
    }

    return max;
};
// @lc code=end