Leetcode 85. Maximal Rectangle(python)

题目

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:
Input:
[
[“1”,“0”,“1”,“0”,“0”],
[“1”,“0”,“1”,“1”,“1”],
[“1”,“1”,“1”,“1”,“1”],
[“1”,“0”,“0”,“1”,“0”]
]
Output: 6

解法1：DP + brutal force（TLE）

• 先用dp求出在每一个位置上，以这个位置为右边界形成的最大宽度
• 从这个位置开始，向上遍历每行的这个位置，取这些位置中形成的最大宽度中的最小值，类似于横过来的largest rectangle
• 这样就可以求出以这个位置作为right bottom corner的rectangle的最大值
• 遍历每个位置，求出这些矩形中的最大值

class Solution(object):def maximalRectangle(self, matrix):""":type matrix: List[List[str]]:rtype: int"""if not matrix:return 0M = len(matrix)N = len(matrix[0])dp = [[0]*N for _ in range(M)]maxarea = 0for i in range(M):for j in range(N):if matrix[i][j] == '0': continuedp[i][j] = dp[i][j-1] + 1 if j else 1width = dp[i][j]for k in range(i,-1,-1):width = min(width,dp[k][j])maxarea = max(maxarea, width*(i-k+1))return maxarea

时间复杂度：O(M^2N), M为matrix的行数，N为matrix的列数
空间复杂度：O(MN)

解法2：利用leetcode 84. Largest Rectangle in Histogram的方法

将matrix按照行转化成histogram，对每一行及以上的matrix形成的histogram利用leetcode 84的方法就可以了

class Solution(object):def maximalRectangle(self, matrix):""":type matrix: List[List[str]]:rtype: int"""def helper(heights):stack = []maxarea = 0heights.append(0)n = len(heights)for i in range(n):if not stack or heights[i]>heights[stack[-1]]:stack.append(i)else:while stack and heights[i]<=heights[stack[-1]]:h = heights[stack[-1]]stack.pop()w = i if not stack else i-stack[-1]-1maxarea = max(maxarea,h*w)stack.append(i)return maxareaif not matrix:return 0maxarea = 0dp = [0] * len(matrix[0])for i in range(len(matrix)):for j in range(len(matrix[0])):dp[j] = dp[j] + 1 if matrix[i][j] == '1' else 0maxarea = max(maxarea,helper(dp))return maxarea

时间复杂度：O(M*N), M为matrix的行数，N为matrix的列数
空间复杂度：O(N)

解法3：DP + 左右扫描线

• 从每一个坐标，向上扫描找出最大的height
• 向左扫描找到左边界
• 向右扫描找出右边界
• 这个位置j形成的最大面积为height[j] * (right[j] - left[j])

class Solution(object):def maximalRectangle(self, matrix):""":type matrix: List[List[str]]:rtype: int"""if not matrix:return 0m = len(matrix)n = len(matrix[0])left = [0]*nright = [n]*nheight = [0]*nmaxarea = 0for i in range(m):curr_left = 0curr_right = n for j in range(n):if matrix[i][j] == '1':height[j] += 1else:height[j] = 0for j in range(n):if matrix[i][j] == '1':left[j] = max(left[j],curr_left)else:left[j] = 0curr_left = j+1for j in range(n-1,-1,-1):if matrix[i][j] == '1':right[j] = min(right[j],curr_right)else:right[j] = ncurr_right = jfor j in range(n):maxarea = max(maxarea, height[j]*(right[j]-left[j]))return maxarea

时间复杂度：O(M*N), M为matrix的行数，N为matrix的列数
空间复杂度：O(N)
关于三种方法的详细解答，参见leetcode的官方解法