T85.最大矩阵

monotonic stack, dp, https://leetcode.cn/problems/maximal-rectangle/description/

给定一个仅包含 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'

这个问题可以转化成多个“柱状图中的最大矩形”（LeetCode 84题）问题。

解题思路

1. 转化问题：我们可以把矩阵的每一行作为“地面”，从地面向上连续的 '1' 形成的长度看作是“柱子”的高度。
2. 动态更新高度：
   • 遍历矩阵的每一行。
   • 维护一个数组 heights，其中 heights[j] 表示第 j 列在当前行及以上连续的 '1' 的个数。
   • 如果 matrix[i][j] == '1'，则 heights[j] += 1。
   • 如果 matrix[i][j] == '0'，则 heights[j] = 0（因为矩形必须是连续的，遇到 '0' 必须断开）。
3. 计算最大矩形：
   • 对于每一行更新完的 heights 数组，它就是一个标准的柱状图。
   • 利用单调栈（Monotonic Stack）算法，在 $O(cols)$ 的时间内算出该柱状图中最大的矩形面积。
4. 全局最大值：在遍历每一行的过程中，不断更新全局最大面积。

Python 代码实现

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        
        rows = len(matrix)
        cols = len(matrix[0])
        heights = [0] * cols
        max_area = 0
        
        for i in range(rows):
            for j in range(cols):
                # 更新当前行各列的高度
                if matrix[i][j] == '1':
                    heights[j] += 1
                else:
                    heights[j] = 0
            
            # 计算以当前行为底的最大矩形面积 (LeetCode 84 题逻辑)
            max_area = max(max_area, self.largestRectangleArea(heights))
            
        return max_area

    def largestRectangleArea(self, heights: List[int]) -> int:
        """
        使用单调栈计算柱状图中最大的矩形面积
        """
        # 在左右两端加哨兵节点，简化边界处理
        h = [0] + heights + [0]
        stack = []
        res = 0
        
        for i in range(len(h)):
            # 如果当前高度小于栈顶高度，说明找到了栈顶高度的右边界
            while stack and h[i] < h[stack[-1]]:
                cur_height = h[stack.pop()]
                # 栈顶被弹出后，现在的栈顶就是左边界
                width = i - stack[-1] - 1
                res = max(res, cur_height * width)
            stack.append(i)
            
        return res

复杂度分析

• 时间复杂度：$O(rows\times cols)$。
  • 我们遍历了矩阵的每一行（$rows$ 次）。
  • 在每一行中，更新高度需要 $O(cols)$，计算单调栈需要 $O(cols)$。
  • 总时间为 $O(rows\times cols)$。
• 空间复杂度：$O(cols)$。
  • 需要一个 heights 数组存储每一列的高度，以及一个单调栈。它们的长度都是列数 $cols$。

这是“最大矩形 (Maximal Rectangle)”问题，核心思路是：将每一行当作“直方图底部”，用单调栈方法（largest rectangle in histogram）求解。 每行都更新“柱状高度”，再用栈求最大矩形面积。

---

✅ 思路详解

1. 构造柱状图高度数组 heights

   • 对于每一行：

     • 若当前格为 '1'，heights[j] += 1

     • 否则（为 '0'），heights[j] = 0

   • 这样，heights[j] 表示从当前行向上连续 '1' 的个数。

2. 用单调栈求“柱状图最大矩形面积”

   • 对每一行的 heights，用经典的“柱状图最大矩形面积”算法：

     • 栈中保存递增高度的下标；

     • 当遇到更小的高度时，不断弹出并计算面积；

     • 面积 = 高度 × (当前下标 - 栈顶下标 - 1)。

3. 取所有行的最大面积。

---

✅ 代码实现（精简+高效）

 class Solution:  
     def maximalRectangle(self, matrix: List[List[str]]) -> int:  
         if not matrix or not matrix[0]:  
             return 0  
           
         n, m = len(matrix), len(matrix[0])  
         heights = [0] * (m + 1)  # +1 保证最后能清空栈  
         max_area = 0  
           
         for row in matrix:  
						 # 更新当前行的高度  

             for j in range(m):  
                 heights[j] = heights[j] + 1 if row[j] == '1' else 0  
               
             stack = [-1]  
             for i in range(m + 1):  
                 while heights[i] < heights[stack[-1]]:  
                     h = heights[stack.pop()]  
                     w = i - stack[-1] - 1  
                     max_area = max(max_area, h * w)  
                 stack.append(i)  
           

             # 每行都更新最大矩形面积  

         return max_area

复杂度分析

• 时间复杂度： O(rows × cols) 每个元素入栈出栈各一次。

• 空间复杂度： O(cols) 只用一个栈和一维高度数组。

Q: heights = [0] * (m + 1) # +1 保证最后能清空栈。多一个？stack = [-1]？

非常好的问题 👍 你提到了两个关键实现细节：

heights = [0] * (m + 1) stack = [-1]

这两个细节是单调栈算法的关键补丁，理解它们可以帮你写出更健壮的版本。 下面我逐步解释为什么“多一个高度”和“栈以 -1 开始”是必要的。

---

🧩 一、heights = [0] * (m + 1) 为什么要多一个？

🎯 目的：保证最后能把栈“清空”

单调栈算法的核心逻辑是：

while heights[i] < heights[stack[-1]]:
     h = heights[stack.pop()]
     w = i - stack[-1] - 1
     max_area = max(max_area, h * w)

问题是： 如果我们只循环到 m - 1，那么最后可能还有上升的柱子留在栈里（还没弹出）。

例如：

heights = [2, 3, 4]

到最后 i=2 时都没触发弹栈，因为高度递增。 这样就会漏掉「以最后柱子结尾」的矩形。

✅ 解决方法： 在最后人为补一个高度 0，保证最后所有的柱子都被弹出计算：

heights = [2, 3, 4, 0]

当 i=3 时，0 < 4，0 < 3，0 < 2，全部弹出 → 计算完整。

---

🧩 二、stack = [-1] 为什么要以 -1 开始？

🎯 目的：简化宽度计算公式，避免边界判断

每次我们计算宽度时用：

w = i - stack[-1] - 1

如果栈是空的怎么办？ 比如第一个柱子 i=0 时就弹栈——没有左边界，这时应该从最左边开始计算宽度。

我们可以让栈底永远放一个“哨兵下标 -1”，表示在最左边界的前一个位置。

这样：

• 对第一个柱子（索引0）来说，宽度 = i - (-1) - 1 = i

• 对中间柱子来说，宽度自动成立

✅ 这样避免了判断“如果栈空则宽度=i”这种分支逻辑。

---

🧠 举例验证

假设 heights = [2,1]

• 初始：stack = [-1]

• i=0, heights[0]=2 → 栈变 [-1,0]

• i=1, heights[1]=1 < heights[0]=2 → 弹出：

  • h=2, w=1 - (-1) - 1 = 1 → 面积 = 2×1=2

• 然后 push(1)，栈 = [-1,1]

• 最后 i=2(虚拟0)，弹出 h=1, w=2 - (-1) - 1 = 2 → 面积 = 1×2=2

正确结果 ✅

---

✅ 总结

机制	用途	作用
heights = [0]*(m+1)	尾部补 0	确保最后清栈计算完所有矩形
stack = [-1]	左边哨兵	让宽度公式 i - stack[-1] - 1 永远成立，无需分支