Leetcode 85. Maximal Rectangle

原题地址

https://leetcode.com/problems/maximal-rectangle/description/

题意

给定一个01矩阵，找出其中最大的由1构成的矩形，返回它的面积。

思路

和上一题最大子方阵类似，同样是构造一个表格dp,dp[i ][ j]存储以元素（i，j）为最右下角的矩形的最大相关的信息，方阵的话只需要边长即可，而这里是矩形，所以我是建了个结构体data，就存水平方向的长度和竖直方向的长度

    struct data {
        int h;
        int v;
    };

在逐步构造dp表的过程中，要得到dp[i][j]的值，每次考虑3种情况：

1. 水平方向长度为1，只考虑竖直方向上能达到多长。
2. 竖直方向长度为1，只考虑水平方向上能达到多长。
3. 根据dp[i-1][j-1]的值，考虑往水平竖直两个方向同时扩展能达到的最大面积。

取以上3种情况中使得面积最大的那一种情况填入dp[i][j]

代码

class Solution {
public:
    struct data {
        int h;
        int v;
    };

    int maximalRectangle(vector<vector<char> >& matrix) {
        int row = matrix.size();
        int area = 0;
        if (row == 0) return 0;
        int col = matrix[0].size();
        if (col == 0) return 0;
        data initial;
        initial.h = 0;
        initial.v = 0;
        vector<vector<data> > dp(row, vector<data>(col, initial));

        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0].h = 1;
                if (i == 0) {
                    dp[i][0].v = 1;
                } else {
                    dp[i][0].v = dp[i - 1][0].v + 1;
                }
            } else {
                dp[i][0].h = 0;
                dp[i][0].v = 0;
            }
            if (dp[i][0].v * dp[i][0].h > area) {
                area = dp[i][0].v * dp[i][0].h;
            }
        }

        for (int i = 0; i < col; i++) {
            if (matrix[0][i] == '1') {
                dp[0][i].v = 1;
                if (i == 0) {
                    dp[0][i].h = 1;
                } else {
                    dp[0][i].h = dp[0][i - 1].h + 1;
                }
            } else {
                dp[0][i].h = 0;
                dp[0][i].v = 0;
            }
            if (dp[0][i].v * dp[0][i].h > area) {
                area = dp[0][i].v * dp[0][i].h;
            }
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == '0') {
                    dp[i][j].h = 0;
                    dp[i][j].v = 0;
                    continue;
                } else {
                    dp[i][j].h = 1;
                    dp[i][j].v = 1;
                }
                int h1 = 1, v1 = 1, h2 = 1, v2 = 1, h3 = 1, v3 = 1;
                int index=1;
                while(j-index>=0 && matrix[i][j-index]=='1'){
                    h1++;
                    index++;
                }
                index =1;
                while(i-index >=0 && matrix[i-index][j]=='1'){
                    v2++;
                    index++;
                }
                int hextend = dp[i - 1][j - 1].h;
                int vextend = dp[i - 1][j - 1].v;
                for (int k = 1; k <= hextend; k++) {
                    if (matrix[i][j - k] == '1') {
                        h3++;
                    } else {
                        break;
                    }
                }
                for (int k = 1; k <= vextend; k++) {
                    if (matrix[i - k][j] == '1') {
                        v3++;
                    } else {
                        break;
                    }
                }
                if (h3 * v3 >= h2 * v2 && h3 * v3 >= h1 * v1) {
                    dp[i][j].h = h3;
                    dp[i][j].v = v3;
                } else if (h2 * v2 > h3 * v3 && h2 * v2 > h1 * v1) {
                    dp[i][j].h = h2;
                    dp[i][j].v = v2;
                } else {
                    dp[i][j].h = h1;
                    dp[i][j].v = v1;
                }
                if (dp[i][j].h * dp[i][j].v > area) {
                    area = dp[i][j].h * dp[i][j].v;
                }
            }
        }
        return area;
    }
};