leetcode 85. Maximal Rectangle-蒲公英云

leetcode 85. Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

class Solution {
    void get_bigger(vector<vector<char>>& matrix, int leftupX, int leftupY, int&maxsquare)
    {
        int kxmin = -1; bool xup(true), yup(true);
        for (int ky = 0; ky + leftupY < matrix.size(); ky++)
        {
            if (matrix[ky + leftupY][leftupX] == '0')
                break;
            int kx = 0;
            while (leftupX + kx<matrix[0].size()&&matrix[ky + leftupY][leftupX + kx]=='1')
                kx++;
            kx--;
            if (kxmin == -1)
                kxmin = kx;
            if (kx < kxmin)
                kxmin = kx;
            if ((1 + kxmin)*(1 + ky)>maxsquare)
                maxsquare = (1 + kxmin)*(1 + ky);
        }
    }
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty())
            return 0;
        if (matrix[0].empty())
            return 0;
        int maxarea = 0;
        for (int i = 0; i < matrix.size(); i++)
            for (int j = 0; j < matrix[0].size(); j++)
            {
                if (matrix[i][j] == '1')
                {
                    get_bigger(matrix, j, i, maxarea);
                }
            }
        return maxarea;
    }
};