Basic idea: scan each row top-down and store in buf the consecutive 1s at colunm j (the height). Then scan buf again to find consecutive 1s in each row (store in region), and calculate the currentMax based on min of buf value within that region. Update currentMax by scanning likewise for each row.
Test is passed for most cases but ouput 110 at 56th test case (100*100 matrix), however the result is 114. Anybody can see any fault of my code?? Thanks!
class Solution: # @param matrix, a list of lists of 1 length string # @return an integer def maximalRectangle(self, matrix): nRows = len(matrix) if not nRows: return 0 nCols = len(matrix) currentMax = 0 if not nCols: return 0 buf =  * nCols # build as buf for i in range(nRows): for j in range(nCols): if matrix[i][j] != '0': buf[j] += 1 else: buf[j] = 0 currentMax = self.calcMax(buf, currentMax) return currentMax def calcMax(self, buf, currentMax): region =  for x in buf: if x != 0: region.append(x) else: region, currentMax = self.calRegionMax(region, currentMax) # do not forget the last row case # print region region, currentMax = self.calRegionMax(region,currentMax) return currentMax def calRegionMax(self, region, currentMax): while region: currentMax = max(len(region)*min(region), currentMax) if region < region[-1]: region = region[1:] elif region > region[-1]: region.pop() else: # compare nearest element thru middle point i = 0 j = len(region)-1 while i<=j: if region[i] > region[j]: region = region[:-1] break elif region[i] < region[j]: region = region[1:] break else: i += 1 j -= 1 if i>j :region = region[1:] # break tie return region, currentMax
Please try resubmit your code again, I have added new test cases to help you debug.
For the following test case, the answer is
6, but your code returns
1101 1101 1111
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.