[매트릭스 2차원 또는 3차원 dp] 최대 하위 매트릭스, 하위 매트릭스 빠른 구화(최대 직사각형 사용)

Maximal Rectangle

 
Total Accepted: 9039 
Total Submissions: 41503 My Submissions
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
세 가지 추이 방법:
1 maxR[i][j]=max{  minHCnt(k...j)*(j+1-k)  }, k=0...j 가지치기 주의.hCnt[k-x]>hCnt[k]일 때 hCnt[k]를 삭제할 수 있습니다.선형 스캐닝 방법으로 가지치기 (112ms)
2 maxR[i][k][j]=maxR[i-1][k][j]+(j+1-k), 그 중에서arr[i][k~j]는 모두'1'이어야 한다.그렇지 않으면 maxR[i][k][j]=0.(72ms)
3 maxR[i][j] = maxHistogram {maxHCntOne[k...i][j]}, 그 중에서 maxHCntOne과 maxHistogram은 O(n)이고 전체 알고리즘은 O(n^n)이다.
방법1:
list가 loop을 반대로 하고 삭제한 쓰기 방법을 주의하십시오!

class Solution {
public:
#define MAXN 200000
    //    +3 dp
    int maximalRectangle(vector > &matrix) {
        int n=matrix.size();if(n==0) return 0;
        int m=matrix[0].size();if(m==0) return 0;
        vector > hCnt(n,vector(m,0));
        for(int j=0;j0?hCnt[i-1][j]+1:1;
                else hCnt[i][j]=0;
            }
        }
        
        //find the largest rect from hCnt[i][j]
        int mR=0;
        typedef pair Pr;
        for(int i=0;i tmp;
            for(int j=0;jhCnt[i][j+1]||j==0||hCnt[i][j]>hCnt[i][j-1]) //h[i][j] is not a extremal small value @@@error:j==0 fault as i==0
                    tmp.insert(tmp.begin(),Pr(j,hCnt[i][j]));
                if(tmp.empty()) continue;///@@@error: must consider list empty, then the for loop will not work
                for(list::iterator k=(--tmp.end());;k--){
                    int t=min(hCnt[i][j],k->second);
                    if(t>mH){
                        k->second= mH=t;
                        mR=max(mR,mH*(j-k->first+1));
                    }
                    else {//erase
                        tmp.erase(k++);//@@warning:after erase, k point to next node (or end())
                    }
                    //after handling the last element(tmp.begin()),break
                    if(k==tmp.begin()) break;
                }
            }
        }
        return mR;
    }
};

방법2:

class Solution {
public:
    int maximalRectangle(vector > &matrix) {
        int L=matrix.size();
        if(L<=0) return 0;
        int R=matrix[0].size();
        int R2=R*R;
        int *height=new int [R*R*2];
        memset(height,0,sizeof(int)*2*R*R);
        int max=0;
        for(int i=0;i

방법3:

class Solution {
public:
    int maximalRectangle(vector > &matrix) {
        int n = matrix.size();
        if(!n) return 0;
        int m = matrix[0].size();
        if(!m) return 0;
        
        vector > lines(n, vector(m, 0));
        int maxArea = 0;
        
        for(int i = 0; i0? lines[i-1][j]:0; //@error: j>0? lines[i][j-1]
                if(matrix[i][j]=='1') lines[i][j] = t+1;
                else lines[i][j] = 0;
            }
            
            // max rectangle in lines[i][0, m-1]
            stack > ss;
            int tmp = 0;
            for(int j = 0; j<=m; j++){
                int t = j==m? -1 : lines[i][j], s = 0;
                while(!ss.empty() && ss.top().first>= t){
                    s+= ss.top().second;
                    tmp = max(tmp, ss.top().first*s);
                    ss.pop();
                }
                ss.push(pair(t, s+1));
                tmp = max(tmp, t*(s+1));
            }
            
            maxArea = max(maxArea, tmp);
        }
        
        return maxArea;
    }
};

하위 행렬 구화

하나의 매트릭스 A[m][n] 하위 매트릭스와 빠른 구법 (업데이트 A[x][y] 및 조회 포함
Sum(i1, j1, i2, j2)):
1B[I][J]는 서브매트릭스: A[0][0]에서 A[I][J]까지의 합을 나타낸다.Sum(i1,j1,i2,j2)=B[i2][j2]-B[i2][j1]-B[i1][j2]+B[i1][j1],
조회 복잡도 O(1),
업데이트 복잡도: A[x][y]가 변할 때 B[x, m-1][y, n-1]는 모두 업데이트가 필요합니다. 복잡도 O(n^2)
2B[I][J]는 행 B[I][0]에서 B[I][J]까지의 합을 나타낸다. 그러면
Sum(i1,j1,i2,j2)=E(B[i1,i2][j2]-B[i1,i2][j1])
질의 복잡성 O(n)
업데이트 복잡성 O(n)
3 상기 변형, B[I]는 하나의 라인 트리로 변하여 이 줄의 구간과 유지한다.
그러면 Sum(B[I][j1<=j<=j2)은 B[I] 이 라인 나무의 구간 구화(O(lgn))로 변하여 T[I]로 기록할 수 있다. 
그러면
Sum(i1, j1, i2, j2) = E(T[i1, i2])(O(n*lgn) )
조회 복잡도 O (nlgn)
업데이트 복잡성 O(1)
4 상기 변형,
B[I]는 하나의 라인 트리가 되어 C[I][j](=sum(A[0, I][j])의 구간과
영T[I]=B[I][j1, j2](O(lgn)),
Sum(i1,j1,i2,j2)=T[i2]-T[i1](O(lgn))
조회 복잡도 O (lgn)
업데이트 복잡도: A[x][y]가 변할 때 C[x, m-1][y]를 업데이트해야 하고 복잡도 O(n)