最大矩形

题目

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

解答

以行进行切分，height[j]表示在目前的底（第1行）的j位置往上（包括j位置），有多少个连续的1。
对于每一次切割，都利用更新后的height数组来求出以当前行为底的情况下，最大的矩形是什么。那么这么多次切割中，最大的那个矩形就是我们要的答案。

问题转化成：每次切分后，如何求最大矩形的面积？

● 第1根高度为3的柱子向左无法扩展，它的右边是2，比3小，所以向右也无法扩展，则以第1根柱子为高度的矩形面积就是31==3；
● 第2根高度为2的柱子向左可以扩1个距离，因为它的左边是3，比2大；右边的柱子也是3，所以向右也可以扩1个距离，则以第2根柱子为高度的矩形面积就是23==6；
● 第3根高度为3的柱子向左没法扩展，向右也没法扩展，则以第3根柱子为高度的矩形面积就是31==3；
● 第4根高度为0的柱子向左没法扩展，向右也没法扩展，则以第4根柱子为高度的矩形面积就是01==0；

因此，对于当前柱子为高度形成的矩阵的面积，要找到距离距离该柱子 左右距离最近，且它高度小的位置（短板决定不能继续扩张了）。
这个过程怎么计算快呢？单调栈
**

代码

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        maxArea = 0
        height = [0] * len(matrix[0])
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                height[j] = height[j] + 1 if matrix[i][j] == '1' else 0
            print(height)
            maxArea = max(maxArea, self.maxRecFromBottom(height))
        return maxArea
    def maxRecFromBottom(self, height):
        if not any(height):
            # 全是0
            return 0
        stack = []
        maxArea = 0
        for i in range(len(height)):
            while stack and height[i] <= height[stack[-1]]:
                j = stack.pop()
                k = stack[-1] if stack else -1
                curArea = (i - k - 1) * height[j]
                maxArea = max(maxArea, curArea)
            stack.append(i)
        while stack:
            j = stack.pop()
            k = stack[-1] if stack else -1
            curArea = (len(height) - k - 1) * height[j]
            maxArea = max(maxArea, curArea)
        return maxArea