動機
不同的DP不同的難易度
Problem
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: 6Explanation: The maximal rectangle is shown in the above picture.
Example 2:
Input: matrix = []Output: 0
Example 3:
Input: matrix = [[0]]Output: 0
Example 4:
Input: matrix = [[1]]Output: 1
Example 5:
Input: matrix = [[0,0]]Output: 0
Constraints:
rows == matrix.length
cols == matrix[i].length
0 <= row, cols <= 200
matrix[i][j]
is'0'
or'1'
.
Ver1: WA
def p(m):
for i in range(0,len(m)):
print(m[i])
class Solution:
def maximalRectangle(self, m: List[List[str]]) -> int:
if not m:
return 0
m = [[int(x) for x in i] for i in m]
for i in range(0,len(m)):
for j in range(0,len(m[i])):
if j-1 >= 0 and m[i][j] is 1:
m[i][j] += m[i][j-1]
p(m)
print("====")
m.insert(0,[0]*len(m[0]))
p(m)
print("====")
ans = 0
for j in range(0,len(m[0])):
k = 0
for i in range(1,len(m)):
if m[i][j] > 0: # 有直的
k += 1 # 有橫的
if m[i-1][j] >= m[i][j]: # 有大塊的
print("big")
print(i,j,m[i-1][j], m[i][j])
m[i-1][j] = k * min(m[i-1][j], m[i][j])
else:
m[i-1][j] = max(k,m[i][j])
else:
m[i-1][j] = 0
k = 0
ans = max(ans,m[i-1][j])
p(m)
return ans
Ver2: AC
分批算面積
class Solution:
def maximalRectangle(self, m: List[List[str]]) -> int:
if not m:
return 0
m = [[int(x) for x in i] for i in m]
for i in range(0,len(m)):
for j in range(0,len(m[i])):
if j-1 >= 0 and m[i][j] is 1:
m[i][j] += m[i][j-1]
#[print(x) for x in m]
ans = 0
for i in range(0,len(m)):
for j in range(0,len(m[i])):
mr = 999999999 # smallest rectangle
if m[i][j] != 0:
for k in range(i,len(m)):
#print((i,j),(k,j),m[k][j],mr)
if m[k][j] != 0:
mr = min(mr,m[k][j])
ans = max(ans,(k-i+1)*mr)
else:
break
#print(ans,mr)
return ans