a***w
发帖数: 168 | 1 You are given a M x N matrix with 0's and 1's
1. Find the largest square matrix with 1's
2. Find the largest rectangular matrix with 1's
没想出哪种比Brute-force 列举更好的办法，哪位有啥hint？ | b********h
发帖数: 119 | 2 How about dynamic programming?
Let S(i,j) be the largest square that ends at row i, column j.
Then
S(i,j) = 0, if (i,j)==0
= min(S(i-1,j), S(i,j-1)) + 1, if (i,j)==1 && S(i-1,j)!=S(i,j-1)
= S(i-1,j) + 1, if (i,j)==1 && S(i-1,j)==S(i,j-1) && (i-k,j-k)==1
The answer is max(S(i,j)). Time complexity is O(m*n). | n******h
发帖数: 50 | 3 我做不到Time complexity O(m*n)
suppose Matrix is m*n (m
for the largest square, time O(m*m*n), space O(m*n)
for the largest rectangle, time O((m+n)*m*n), space O(m*n*n) | r**u
发帖数: 1567 | 4 这个可以reduce成find max rectangle in柱状图。考古一下。Another hint: 先找到
每行的连续序列。
e.g., convert 1 0 1 1 1 0 --> 1 0 1 2 3 0.
【在 a***w 的大作中提到】
: You are given a M x N matrix with 0's and 1's
: 1. Find the largest square matrix with 1's
: 2. Find the largest rectangular matrix with 1's
: 没想出哪种比Brute-force 列举更好的办法，哪位有啥hint？
|
|
