Accepted 12ms DP solution in c++, similar with what is used in Maximal Rectangle.


  • 0

    This is a DP solution in c++, 12ms, similar with what is used in Maximal Rectangle. Here is the general idea of this solution, it is presented by morrischen2008, thanks for his outstanding work.

    class Solution {
    public:
    	int maximalSquare(std::vector<std::vector<char> > &matrix) {
    		if(matrix.empty())
    			return 0;
    		int rows = matrix.size(), cols = matrix[0].size(), length = 0;
    		std::vector<int> left(cols), right(cols, cols), height(cols);
    		for(int i = 0; i != rows; ++i) {
    			int cur_left = 0, cur_right = cols;
    			for(int j = cols - 1; j >= 0; --j)
    				if(matrix[i][j] == '1')
    					right[j] = std::min(right[j], cur_right);
    				else {
    					right[j] = cols;
    					cur_right = j;
    				}    
    			for(int j = 0; j != cols; ++j)
    				if (matrix[i][j] == '1') {
    					left[j] = std::max(left[j], cur_left);
    					++height[j];
    					length = std::max(length, std::min(right[j] - left[j], height[j]));
    				}
    				else {
    					left[j] = height[j] = 0;
    					cur_left = j + 1;
    				}
    		}
    		return length * length;
    	}
    };
    

Log in to reply
 

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