LeetCode 085 Maximal Rectangle

LeetCode

Given a rows x cols binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.

Example 1:

Input: matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = [[“0”]]
Output: 0

Example 3:

Input: matrix = [[“1”]]
Output: 1

Constraints:

rows == matrix.length cols == matrix[i].length
1 <= row, cols <= 200 matrix[i][j] is '0' or '1'.

题目大意：

0-1矩阵求全部都是1的最大的子矩阵

解题思路：

类似于LeetCode 084 Largest Rectangle in Histogram，按每行生成连续1的直方图，求最大矩形面积。然后逐行调用L084的方法。

解题步骤：

N/A

注意事项：

1. 由于L084的方案是修改原数组，所以不能直接调用，必须修改L084的方法，copy一份数组再往首尾插入0.

Python代码：

def maximalRectangle(self, matrix: List[List[str]]) -> int:
	heights, res = [0] * len(matrix[0]), 0
	for i in range(len(matrix)):
		for j in range(len(matrix[0])):
			if matrix[i][j] == '0':
				heights[j] = 0
			else:
				heights[j] += 1
		area = self.largestRectangleArea(heights)
		res = max(res, area)
	return res

def largestRectangleArea(self, height_list: List[int]) -> int:
	stack, res = [], 0
	heights = list(height_list)
	heights.insert(0, 0) # remember
	heights.append(0)
	for i in range(len(heights)):
		while stack and heights[i] < heights[stack[-1]]:
			index = stack.pop()
			res = max(res, (i - stack[-1] - 1) * heights[index]) # remember i - stack[-1] - 1 not i - index
		stack.append(i)
	return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(m), n, m分别为行数和列数