学步园

三种递推方法：

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<vector<char> > &matrix) {
        int n=matrix.size();if(n==0) return 0;
        int m=matrix[0].size();if(m==0) return 0;
        vector<vector<int> > hCnt(n,vector<int>(m,0));
        for(int j=0;j<m;j++){
            int c=0;
            for(int i=0;i<n;i++){
                if(matrix[i][j]=='1') hCnt[i][j]=i>0?hCnt[i-1][j]+1:1;
                else hCnt[i][j]=0;
            }
        }
        
        //find the largest rect from hCnt[i][j]
        int mR=0;
        typedef pair<int,int> Pr;
        for(int i=0;i<n;i++){
            list<Pr> tmp;
            for(int j=0;j<m;j++){
                int mH=0;
                if(j==m-1||hCnt[i][j]>hCnt[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<Pr>::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<vector<char> > &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<L;i++){
            memset(height+(i%2)*R*R,0,sizeof(int)*R*R);//height[i%2][r][r]=0
            int c=i%2,d=(i+1)%2,tmp;
            for(int j=0;j<R;j++){
                for(int k=j;k<R;k++){
                    if(matrix[i][k]=='0') { break;}
                    else {
                        tmp=height[c*R2+j*R+k]=height[d*R2+j*R+k]+1;
                        max=max<tmp*(k-j+1)?tmp*(k-j+1): max;
                    }
                }
            }
        }
        return max;
    }
};

方法3:

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        int n = matrix.size();
        if(!n) return 0;
        int m = matrix[0].size();
        if(!m) return 0;
        
        vector<vector<int> > lines(n, vector<int>(m, 0));
        int maxArea = 0;
        
        for(int i = 0; i<n; i++){
            // lines[i][j]=maxCntOne(matrix[x, i][j])
            for(int j = 0; j<m; j++){
                int t = i>0? 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<pair<int, int> > 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<int, int>(t, s+1));
                tmp = max(tmp, t*(s+1));
            }
            
            maxArea = max(maxArea, tmp);
        }
        
        return maxArea;
    }
};

子矩阵求和