题目

给定一个仅包含 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”]] 输出：0

示例 3：

输入：matrix = [[“1”]] 输出：1

提示：

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

解题思路

不要试图一眼看出矩阵里的最大矩形，那样太难了。 试想一下，我们把这个矩阵按行切开，一行一行地看。

我们要做的就是：站在每一行上，向上看，统计这一行能作为“地基”撑起多高的柱子。

规则非常简单：

1. 遇 1 累加：如果你头顶上是 1，说明柱子断不了，高度 +1。

2. 遇 0 坍塌：如果你头顶上是 0，不管上面有多高，由于矩形不能断开，这根柱子在这里的高度瞬间变成 0。

举例演示

假设矩阵是这样的：

[
  ["1", "0", "1"],
  ["1", "1", "1"],
  ["1", "1", "1"]
]

我们一行一行构建“柱状图”：

• 第 1 行 (1 0 1):

  • 当前高度数组：[1, 0, 1]

  • 潜台词：这一层有两根高度为1的柱子。

• 第 2 行 (1 1 1):

  • 第1列：上一行是1，现在也是1 -> 高度变 2。

  • 第2列：上一行是0，现在是1 -> 高度变 1（重新开始）。

  • 第3列：上一行是1，现在也是1 -> 高度变 2。

  • 当前高度数组：[2, 1, 2]

• 第 3 行 (1 1 1):

  • 全都是 1，都在原来的基础上 +1。

  • 当前高度数组：[3, 2, 3]

结论：通过这种方式，我们把一个二维矩阵，转化成了 Rows 个一维数组（直方图）。

第二步：微观视角——解决“一行”的问题

现在问题变了：给你一个数组（代表一排柱子的高度），请你在这些柱子里划出一个最大的矩形。

比如处理到最后一行时，数组是 [3, 2, 3]。

我们需要对每一根柱子做一次“灵魂拷问”：

“以你为高度，最宽能扩到哪里？”

1. 看左边的柱子（高度3）：

   • 它向左看：没路了。

   • 它向右看：碰到了高度 2。2 < 3，过不去。

   • 面积 = 3 * 1 = 3。

2. 看中间的柱子（高度2）：

   • 它向左看：左边是 3。3 > 2，可以通过！（在3里面截出2的高度）。

   • 它向右看：右边是 3。3 > 2，可以通过！

   • 结果：它横跨了左中右三根柱子。

   • 面积 = 2 * 3 = 6。

3. 看右边的柱子（高度3）：

   • 逻辑同左边那个 3。

   • 面积 = 3 * 1 = 3。

最大值是 6。

第三步：算法落地——单调栈的介入

在第二步中，如果用肉眼看（或双重循环），我们需要“向左找”、“向右找”。在计算机里，为了快，我们引入了单调栈。

这里的逻辑不需要死记硬背，只需要记住它的功能：

• 为什么要用单调栈？

  • 为了一次遍历就能找到每一根柱子“左边第一个比它矮的”和“右边第一个比它矮的”。

• 怎么运作？

  • 所有柱子排队进栈（按高度从小到大）。

  • 一旦来了一个矮个子，它会挡住栈顶那个高个子的去路。

  • 这时候，高个子就被迫“结算”了：

    • 高 = 它自己。

    • 宽 = 刚才那个矮个子（右边界） - 它的前任（左边界） - 1。

总结：完整解题流

这道题的解法就是把上面三步串起来：

1. 初始化：搞一个 max_area = 0，搞一个长度为 cols 的数组 heights 全是 0。

2. 大循环（遍历每一行）：

   • 更新 heights：如果是 ‘1’ 就 +1，如果是 ‘0’ 就归零。

3. 子任务（计算当前行的最大矩形）：

   • 把当前的 heights 丢给“单调栈算法”。

   • 单调栈算出这一行构成的直方图里最大的面积 area。

4. 打擂台：

   • max_area = max(max_area, area)。

5. 返回 max_area。

这就是这道题从宏观到微观的完整逻辑。它其实是把**“动态规划”（累加高度）和“单调栈”（直方图最大面积）**结合在了一起。

具体代码