来自北大算法课的Leetcode题解：85. 最大矩形

代码仓库：Github | Leetcode solutions @doubleZ0108 from Peking University.

• 解法1(T13% S88%): 动态规划（嵌套一层循环的dp）。思想其实并不复杂，每一个位置看看它能达到的向上最大高度和向左最大宽度，这可以通过一个dp来求，假设获取了这个信息，只需在这个点往左的宽度内依次遍历，每个位置向上取最小高度，并依次计算面积，最终保留最大值即可

  而dp是如何做的呢？可以用两个dp数组分别来做（实测比把两个数组变为一个消耗内存少）

  dp_top[i][j] = dp_top[i-1][j] + 1
  dp_left[i][j] = dp_left[i][j-1] + 1
  1
  2

---

之前错误的想法也记录一下：

最开始想的dp[i][j]=[x,y]代表以i,j为右下角的最大矩形，它的高为x，宽为y，然后依次从正上方(i-1,j)，正左方(i,j-1)，和对角线(i-1,j-1)进行扩展，但会陷入局部最优解，例如这个例子：

0 0 1 0 
0 0 1 0 
0 0 1 0 
0 0 1 1 
0 1 1 1 
0 1 1 1 
1 1 1 1
1
2
3
4
5
6
7

因为只能从旁边的一个位置扩展，最终会陷入右下角24的矩形，而不是33的最大结果中

于是又进行优化，把上面的情况在三个方向分别做，开了三个dp数组top、left、corner，把从每个方向的三种扩展都记录下来，这样就可以防止掉入一个贪婪的局部最大值，但会遇到这个样例：

1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 0 
1 1 1 1 1 1 1 0 
1 1 1 1 1 0 0 0 
0 1 1 1 1 0 0 0
1
2
3
4
5

最终会掉入从00开始的5*5矩形里

于是又在三种扩展中加了向左和向上的循环判断这条边必须全为1

总之最后还是会没法很好的扩展

究其根本，我觉得是没有想到dp也是可以跟循环嵌套着来的，不能觉得循环耗时，一重循环还是很轻量的

class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        m, n = len(matrix), len(matrix[0])

        dp_top = [[0]*(n+1) for _ in range(m+1)]
        dp_left = [[0]*(n+1) for _ in range(m+1)]

        maxArea = 0
        for i in range(1,m+1):
            for j in range(1,n+1):
                if matrix[i-1][j-1] == "1":
                    dp_top[i][j] = dp_top[i-1][j]+1
                    dp_left[i][j] = dp_left[i][j-1]+1

                    minHeight = dp_top[i][j]
                    for k in range(j, j-dp_left[i][j], -1):
                        width = j-k+1
                        minHeight = min(minHeight, dp_top[i][k])
                        maxArea = max(maxArea, minHeight*width)

        return maxArea

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26