leetcode-Maximal Rectangle
제목: 직사각형을 제시하고 그 안에'0'과'1'을 채워서 완전히'1'으로 구성된 최대 자사각형의 면적을 찾아낸다.
분석:저는 dp로 이 문제를 풀었습니다.row[i][j]와col[i][j]로 점(i, j)을 오른쪽 하각으로 하는 전체 1자 직사각형의 행수와 열을 각각 기록한다.right[i][j]와down[i][j]로 (i, j)를 끝으로 왼쪽에서 오른쪽으로 1개 연속, 위에서 아래로 1개 연속을 기록합니다.
각 점(i, j)을 차례대로 훑어보고 고려점(i-1, j)과 (i, j-1)을 고려한다.
점(i-1, j)에 대해 (row[i-1][j]+1)*col[i-1][j]가 단행 연속 1개수인 right[i][j]보다 작은지 고려하고, 작으면 (i, j)를 오른쪽 하각으로 하는 최대 사각형을 이 단행 연결 1로 기록한다.그렇지 않으면 (i-1, j)에 대응하는 직사각형에 현재 줄을 추가하고 열수는min(col[i-1][j],right[i][j])로 기록합니다.
점(i-1, j)에 대해row[i][j-1]*(col[i][j-1]+1)이 단열 연속 1개수down[i][j]보다 작은지 고려하고, 작으면 (i, j)를 오른쪽 하각으로 하는 최대 사각형을 이 단열 연결 1로 기록한다.그렇지 않으면 (i, j-1) 대응 사각형에 현재 열을 추가하고, 줄 수는min(row[i][j-1],down[i][j])로 기록합니다.
상기 두 결과의 비교적 큰 직사각형을 선택하여 (i, j)의 결과로 삼다.
모든 점의 최대 사각형 면적, 즉 결과를 기록합니다.
코드:
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
int n = matrix.size();
if(n==0) return 0;
int m = matrix[0].size();
if(m==0) return 0;
int **row = new int*[n+1];
int **col = new int*[n+1];
int **right = new int*[n+1];
int **down = new int*[n+1];
for(int i=0; i<=n; i++)
{
row[i] = new int[m+1];
col[i] = new int[m+1];
right[i] = new int[m+1];
down[i] = new int[m+1];
memset(row[i],0,sizeof(int)*(m+1));
memset(col[i],0,sizeof(int)*(m+1));
memset(right[i],0,sizeof(int)*(m+1));
memset(down[i],0,sizeof(int)*(m+1));
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(matrix[i][j]=='0') right[i+1][j+1]=0;
else right[i+1][j+1]=right[i+1][j]+1;
}
}
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
if(matrix[j][i]=='0') down[j+1][i+1]=0;
else down[j+1][i+1]=down[j][i+1]+1;
}
}
int ans = 0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(matrix[i-1][j-1]=='1')
{
row[i][j]=1;
col[i][j]=1;
int r1,c1,r2,c2;
if(right[i][j]>(row[i-1][j]+1)*col[i-1][j])
{
r1 = 1;
c1 = right[i][j];
}
else
{
r1 = row[i-1][j]+1;
c1 = min(col[i-1][j],right[i][j]);
}
if(down[i][j]>row[i][j-1]*(col[i][j-1]+1))
{
r2 = down[i][j];
c2 = 1;
}
else
{
r2 = min(row[i][j-1],down[i][j]);
c2 = col[i][j-1]+1;
}
if(r1*c1>r2*c2)
{
row[i][j] = r1;
col[i][j] = c1;
}
else
{
row[i][j] = r2;
col[i][j] = c2;
}
if(row[i][j]*col[i][j]>ans)
ans = row[i][j]*col[i][j];
}
}
}
return ans;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.