讨论/《春招冲刺班 - 7 天刷题挑战》 - 85. 最大矩形/
《春招冲刺班 - 7 天刷题挑战》 - 85. 最大矩形
共 8 个回复

抛砖引玉一下,介绍下我的时间复杂度O(m^2*n)复杂度的做法。

要考虑二维数组中的最大矩形,可以先从每一行开始考虑。计算出数组matrix中第i行里以matrix[i][j]结尾的连续"1"的数量,用一个二维数组f记录下来。

如示例中的matrix:

image.png

它的f数组就是:

image.png

然后对f数组进行列优先遍历,对于f[i][j],我们向上找,由于f[m][j] (0<=m<=i)中存储的是matrix中第m行里以matrix[m][j]结尾的连续"1"的数量,那么从f[m][j]到f[i][j]的i-m+1个元素中的最小值minvalue就是以(i,j)为右下角的矩形的宽,高自然就是i-m+1。循环一直到f[m][j]==0(或者说是matrix[m][j]==0)时结束,说明以(i,j)为右下角的矩形的高最多就是i-m+1了。将这趟循环中面积area=minvalue * (i - m + 1)的最大值记录到一个二维数组areas中,最终areas数组的最大值就是所求结果了。

如示例中的matrix的areas数组就是:

image.png

其中最大元素是6,所以结果是6。

java代码如下:

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) return 0;
        int cols = matrix[0].length;
        if (cols == 0) return 0;
        //二维数组中元素f[i][j]存储记录matrix第i行中,以第j列结尾有几个连续的1
        int[][] f = new int[rows][cols], areas = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            int temp = 0;//temp记录当前第i行中,以第j列结尾有几个连续的1
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1')
                    f[i][j] = ++temp;
                else
                    temp = 0;
            }
        }
        int ans = 0;
        for (int j = 0; j < cols; j++) {
            for (int i = 0; i < rows; i++) {
                int area = 0, minvalue = f[i][j], m = i;
                while (m >= 0 && f[m][j] > 0) {
                    minvalue = Math.min(minvalue, f[m][j]);
                    area = Math.max(area, minvalue * (i - m + 1));
                    m--;
                }
                areas[i][j] = area;
                ans = Math.max(ans, areas[i][j]);
            }
        }
        return ans;
    }
}
6

这里介绍一种悬线法。一般可以再O(nm)O(n*m)的时间复杂度内,解决掉类似于求最大矩形面积,最大矩形周长问题等。

对于(i,j)(i,j)这个点主要维护三个数组L[i][j]L[i][j]往左可扩展到的最大右边界,R[i][j]R[i][j]往右可扩展到的最小左边界,up[i][j]up[i][j]可扩展到的最上面的边界。

递推关系式L[i][j]=max(L[i][j],L[i][j1])L[i][j]=max(L[i][j],L[i][j-1])
R[i][j]=max(R[i][j],R[i][j+1])R[i][j]=max(R[i][j],R[i][j+1])
Up[i][j]=max(Up[i][j],Up[i1][j])Up[i][j]=max(Up[i][j],Up[i-1][j])

对于每个点(i,j)(i,j)三个属性构成的矩形面积为
S=(R[i][j]L[i][j]+1)Up[i][j]S = (R[i][j]-L[i][j]+1)*Up[i][j]

最后的答案遍历n*m个点,求最大ans = max(ans,S)

4

写完发现我的dp数组全是0,右从头看了一遍才发现给的参数是char[][],打脑壳

2

双指针
首先求出每一行1的高度
再通过双指针求面积(用单调栈也行)

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int width = matrix[0].length;
        int height = matrix.length;
        int[] dp = new int[width];
        int area = 0;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (matrix[i][j] == '1') {
                    dp[j]++;
                } else {
                    dp[j] = 0;
                }
            }
            area = Math.max(area, getMax(dp));
        }
        return area;
    }

    public int getMax(int[] height) {
        int len = height.length;
        if (len == 0) {
            return 0;
        }
        int left;
        int right;
        int area = 0;
        for (int i = 0; i < len; i++) {
            if (height[i] == 0) {
                continue;
            }
            left = i;
            right = i;
            //找左边界
            while (left != 0 && height[left - 1] >= height[i]) {
                left--;
            }
            while (right != len - 1 && height[right + 1] >= height[i]) {
                right++;
            }
            area = Math.max(area, height[i] * (right - left + 1));
        }
        return area;
    }
}
1

单调栈

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n=matrix.size();
        if(n==0) return 0;
        int m=matrix[0].size();
        vector<int> height(m,0);
        int ans=0;
        stack<int> q;
        vector<int> l(m);
        vector<int> r(m);
        for(int i=0;i<n;++i) {
            for(int j=0;j<m;++j) {
                if(matrix[i][j]=='1') height[j]++;
                else height[j]=0;
                while(q.size()&&height[q.top()]>height[j]) {
                    r[q.top()]=j-1;
                    q.pop();
                }
                q.push(j);
            }
            while(q.size()) {
                r[q.top()]=m-1;
                q.pop();
            }
            for(int j=m-1;j>=0;--j) {
                while(q.size()&&height[q.top()]>height[j]) {
                    l[q.top()]=j+1;
                    q.pop();
                }
                q.push(j);
            }
            while(q.size()) {
                l[q.top()]=0;
                q.pop();
            }
            for(int j=0;j<m;++j) {
                ans=max(ans,(r[j]-l[j]+1)*height[j]);
            }
        }
        return ans;
    }
};
1

参与“7天刷题挑战”的童鞋欢迎点击问卷加入专属社群哦~
2月1日-7日,字节跳动工程师直播刷题等你来围观

1

C语言 单调栈
1.把每一行处理成类似柱形图 和原来的数据相比,在最后多一个 -1
2.写一个平淡无奇的栈(C语言这个要自己写)
3.
利用单调递增栈 如果下一个元素比栈顶元素大或者相等,那么把 对应的索引进栈
如果下一个元素比栈顶元素小,则while()循环 让之前进栈的索引出栈 并且根据索引和索引对应的值计算面积

typedef struct Stack{
    int numbers[300];
    int top;
    int isEmpty;
}stack;
int getTop(stack* obj){
    if(obj->isEmpty==1)
    return -1;

    return obj->numbers[obj->top-1];
}
stack* createStack(){
    stack* obj=(stack*)malloc(sizeof(stack));
    int i;
    for(i=0;i<300;i++){
        obj->numbers[i]=0;
    }
    obj->isEmpty=1;
    obj->top=1;
    return obj;
}
void push(stack* obj,int x){
    if(obj->isEmpty==1)
    obj->isEmpty=0;
    obj->numbers[obj->top]=x;
    obj->top++;
}
void pop(stack* obj){
    if(obj->isEmpty)
    return;
    if(obj->top==2)
    obj->isEmpty=1;
    obj->top--;
    return;
}
void freeStack(stack* obj){
    free(obj);
}


int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize){
    if(matrixSize==0)
    return 0;
    int trueMatrix[matrixSize][*matrixColSize+1];
    int i,n;
    int max=0;
    int height;
    stack* obj;
    
    for(n=0;n<*matrixColSize;n++){
        trueMatrix[0][n]=(int)(matrix[0][n]-'0');
    }
    trueMatrix[0][n]=-1;
    for(n=1;n<matrixSize;n++){
        for(i=0;i<*matrixColSize;i++){
            trueMatrix[n][i]=matrix[n][i]=='1'?trueMatrix[n-1][i]+1:0;
        }
        trueMatrix[n][i]=-1;
    }
    for(n=0;n<matrixSize;n++){
        obj=createStack();
        for(i=0;i<*matrixColSize+1;i++){
            if(i==0){
                push(obj,i);
            }
            else if(trueMatrix[n][i]>=trueMatrix[n][getTop(obj)]){
                push(obj,i);
            }
            else{
                while(!obj->isEmpty){
                    if(trueMatrix[n][i]<trueMatrix[n][getTop(obj)]){
                    height=trueMatrix[n][getTop(obj)];
                    pop(obj);
                    max=max<height*(i-getTop(obj)-1)?height*(i-getTop(obj)-1):max;
                }
                else break;
                }
                push(obj,i);
            }
        }
        freeStack(obj);
    }
    return max;

}

注意的细节就是如果栈空,返回的用来计算宽度的值是-1,就是说当前的高度比所有之前的元素都要小

这就是悬线呀,和单调栈差不多