動機

不同的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