At each column, we’re trying to create a square with that column as the left side. The largest such square we could possibly create is N - currentColumn.
const int mmap[5][5]=
{
{1,1,0,0,1},
{0,1,0,1,1},
{1,1,1,0,1},
{1,1,1,0,1},
{1,1,1,0,1}
};
1 0 1 0 0
{1,1,0,0,1},
{0,1,0,1,1},
{1,1,1,0,1},
{1,1,1,0,1},
{1,1,1,0,1}
};
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
// Approach#1: Time:O(N*N),SpacE:O(N*N)
int[][] dp = new int[][];
dp[i][j] = matrix[i][j] = 1 ? min( min(dp[i-1][j], dp[i][j-1]) , dp[i-1][j-1] )
: 0;
.
.
dp[i-1][j-1] dp[i-1,j]
dp[i,j-1] 1
max = Math.max(max, dp[i][j]);
return (int)Math.pow(max, 2);
NOTE: need [i-1][j-1] so initialize [0][j] and [i][0]
//Approach#2 Time:O(N*N),SpacE:O(N)
// Approach#1: Time:O(N*N),SpacE:O(N*N)
int[][] dp = new int[][];
dp[i][j] = matrix[i][j] = 1 ? min( min(dp[i-1][j], dp[i][j-1]) , dp[i-1][j-1] )
: 0;
.
.
dp[i-1][j-1] dp[i-1,j]
dp[i,j-1] 1
max = Math.max(max, dp[i][j]);
return (int)Math.pow(max, 2);
NOTE: need [i-1][j-1] so initialize [0][j] and [i][0]
//Approach#2 Time:O(N*N),SpacE:O(N)
int[] heights = new int[matrix[0].length];
heights[j] = (i==0)? matrix[i][j]
: height[j] + matrix[i][j]
int curArea = largestArea(heights);
maxArea = Math.max(curArea, maxArea);
: height[j] + matrix[i][j]
int curArea = largestArea(heights);
maxArea = Math.max(curArea, maxArea);
NOTE: stack keep those with smaller height
height = previous height SINCE smaller height would dominate
so keep the idnex with smaller height and
width = current - precious precvious's index
if previous index is 0 then set is as -1
otherwise, previous precious index
h 1 2 3 4
|
| |
| | |
| | | |
-----------------
i 0 1 2 3
height = h[0]
width = len -(-1)-1 = len
max= height* height since height < width
h 1 4 3 2
|
| |
| | |
| | | |
-----------------
i 0 1 2 3
i = 2, h[2] <= h[1]
index = 1
height = h[1] =4
preIndex = 0;
width = 2(i)-0(preIndex)-1 = 1;
maxArea = 1*1=1
put 2 in stack
i=3
index = 2
height = h[2] = 3
preIndex = 0
width = 3 - 0 - 1 =2
maxArea = 2*2=4
2. implementation
// Time:O(N*N),SpacE:O(N)
public int maximalSuqare(int[][] matrix)
{
// validate the input
if ( matrix == null || matrix.length ==0 || matrix[0].length ==0 )
return 0;
int[] heights = new int[matrix[0].length];
int maxArea = 0;
for (int i = 0 ; i < matrix.length; i++)
{
for (int j = 0 ; j < matrix[0].length ; j ++)
{
if (matrix[i][j] ==1 )
heights[j] +=1;
else
heights[j] = 0;
}
int curArea = largestArea(heights);
maxArea = Math.max(curArea, maxArea);
}
}
// Idea: Compare with previous height, if less than we calculate
private int largestArea(int[] heights)
{
int maxArea = 0;
LinkedList stack = new LinekdList();
for (int i = 0; i < heights.length; i++)
{
while ( !stack.isEmpty() && heights[i] <= heights[stack.peek()] )
{
NOTE: stack keep those with smaller height
int index = stack.pop();
int height = heights[index];
int preIndex = stack.isEmpty() ?-1: stack.peek();
int width = i - preIndex -1;
maxArea = Math.max(maxArea, height < width? height*height: width:width);
}
NOTE: stack keep those with smaller height
stack.push(i);
}
while (!stack.isEmpty())
{
int index = stack.pop();
int height = heights[index];
int preIndex = stack.isEmpty() ?-1: stack.peek();
int width = heights.length - preIndex -1;
maxArea = Math.max(maxArea, height < width? height*height: width:width);
}
return maxArea;
}
// Time:O(N*N),SpacE:O(N*N)
public int maximalSquare(int[][] matrix)
{
// validate the input
if (matrix == null || matrix.length ==0 )
return 0;
int[][] dp = new int[matrix.length][matrix[0].length];
int max = 0;
for (int i = 0; i < matrix.length; i++) {
dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
max = Math.max(max, dp[i][0]);
}
for (int j = 0; j < matrix[0].length; j++) {
dp[0][j] = matrix[0][j] == '1' ? 1 : 0;
max = Math.max(max, dp[0][j]);
}
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
dp[i][j] = matrix[i][j] == '1' ?
Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1 : 0;
max = Math.max(max, dp[i][j]);
}
}
return max*max;
}
public static SubSquare findSquare( int[] matrix )
{
// validate the input
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return null;
int N = matrix.length;
int currentMaxSize = 0;
SubSquare sq = null;
int col = 0;
// STEP1: iterate through each column from left to right
while ( N - col > currentMaxSize )
{
for (int row = 0; row < N; row++)
{
// strating from the biggest
int size = N - Max.max(row, col);
while ( size > currentMaxSize )
{
if ( isSquare(martix, row, col, size) )
{
currentSize = size;
sq = new SubSquare(row, col,size);
break;
}
size--;
}
}
col++;
}
}
private static boolean isSquare (int[][] matrix, int row, int col, int size)
{
// Check top and bottom border, --->, down
// Extend by offset (the size)
// <------col------>
// |
// |
// |
for (itn j = 0; j < size ; j ++)
{
if ( matrix[row][col+j] == 1)
return false;
if ( matrix[row+size-1][col+j]==1)
return false;
}
// Check left and right border
// Extend by offset (the size)
// ----->
// |
// |
// |
// --->
for(int i =0; i < size -1;i++)
{
if ( matrix[row+i][col] == 1)
return false;
if ( matrix[row+i][col+size-1] ==1 )
return false;
}
return true;
}
public class SubSquare
{
public int row, column, size;
public Subsquare(int r, int c, int s)
{
row = r;
column = c;
size = s;
}
}
3. Similar Oneshttp://massivealgorithms.blogspot.com/2014/07/maximum-size-square-sub-matrix-with-all.html
http://jeffmeng.com/imagine-there-is-a-square-matrix-with-n-x-n-cells-each-cell-is-either-filled-with-a-black-pixel-or-a-white-pixel-design-an-algorithm-to-find-the-maximum-subsquare-such-that-all-four-borders-are-fill/
http://massivealgorithms.blogspot.com/2014/07/maximum-size-square-sub-matrix-with-all.html
No comments:
Post a Comment