My DP solution using C++


  • 0
    M

    In my code, the flag contains the numbers of the largest lists containing only 1's in the right and the top of matrix[i][j], and that is first and second variables of pair<int, int> in code.Then i decide to find the largest rectangle that contains matrix[i][j] in lower right corner .

    class Solution {
    public:
        int maximalRectangle(vector<vector<char>>& matrix) {
            if (matrix.empty() || matrix[0].empty()) return 0;
    	int m = matrix.size(), n = matrix[0].size();
    	vector<vector<pair<int, int>>> flag(m, vector<pair<int, int>>(n));
    	int maxRct = 0;
    	for (int i = 0; i<m; i++)
    	{
    	    for (int j = 0; j<n; j++)
    	    {
    		if (matrix[i][j] == '0')
    		    flag[i][j].second = flag[i][j].first = 0;
    		else
    		{
    		    flag[i][j].first = j == 0 ? 1 : flag[i][j-1].first + 1;
    		    flag[i][j].second = i == 0 ? 1 : flag[i-1][j].second + 1;
    		    int first = flag[i][j].first;
    		    for (int m = i; m >= 0 && flag[m][j].first > 0; m--)
    		    {
    			first = min(first, flag[m][j].first);
    			maxRct = max(maxRct, first*(i-m+1));
    		    }
    		}
    	    }
    	}
    	return maxRct;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.