1. 概述

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

示例：

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

1.1 思路

1.1.1 递增栈

1. 计算出每行向上累积的高度
2. 对每行的高度做一次取最大矩形（leetcode-84题：柱状图通过单调递增栈找到最大矩形）
3. 对比行柱状图的最大矩形，取出最大矩形

   2. 解题

   ```php <?php

class Solution { /**

 * @param Integer[][] $matrix
 * @return Integer
 */
public function maximalRectangle($matrix)
{
    $max = $this->largestRectangleArea($matrix[0]);
    for ($i = 1; $i < count($matrix); $i++) {
        for ($j = 0; $j < count($matrix[0]); $j++) {
            ($matrix[$i][$j]) && $matrix[$i][$j] += $matrix[$i - 1][$j];
        }
        $max = max($max, $this->largestRectangleArea($matrix[$i]));
    }
    return $max;
}
/**
 * leetcode-84 柱状图中最大的矩形
 * @param Integer[] $heights
 * @return Integer
 */
private function largestRectangleArea($heights)
{
    if (!$heights) return 0;
    $n = count($heights);
    $increaseStack = new SplStack();
    // 通过递增栈来确定 左边界
    $rightMargin = $leftMargin = [];
    for ($i = 0; $i < $n; $i++) {
        while (!$increaseStack->isEmpty() && $heights[$increaseStack->top()] >= $heights[$i]) {
            $increaseStack->pop();
        }
        $leftMargin[$i] = $increaseStack->isEmpty() ? -1 : $increaseStack->top();
        $increaseStack->push($i);
    }
    // 通过递增栈来确定 右边界
    $reduceStack = new SplStack();
    for ($j = $n - 1; $j >= 0; $j--) {
        while (!$reduceStack->isEmpty() && $heights[$reduceStack->top()] >= $heights[$j]) {
            $reduceStack->pop();
        }
        $rightMargin[$j] = $reduceStack->isEmpty() ? $n : $reduceStack->top();
        $reduceStack->push($j);
    }
    // 计算最大矩形
    $answer = 0;
    for ($i = 0; $i < $n; $i++) {
        $answer = max($answer, ($rightMargin[$i] - $leftMargin[$i] - 1) * $heights[$i]);
    }
    return $answer;
}

}

$matrix = [ [“1”, “0”, “1”, “0”, “0”], [“1”, “0”, “1”, “1”, “1”], [“1”, “1”, “1”, “1”, “1”], [“1”, “0”, “0”, “1”, “0”] ]; $cls = new Solution(); $ret = $cls->maximalRectangle($matrix); echo $ret; ```