85.MaximalRectangle.md

题目描述
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

难度系数
Hard

解法：先横向求解而后纵向求解

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return 0;

        int rt = 0;
        //横向遍历，将连续的1的个数相加到后面，确定长方形的长
        for(int i=0; i<matrix.size(); i++){
            for(int j=1; j<matrix[0].size(); j++){
                if(matrix[i][j] != '0')
                    matrix[i][j] += (matrix[i][j-1]-48);
            }
        }
        //纵向遍历，以各点为右边界，寻找长方形的宽
        for(int j=matrix[0].size()-1; j>=0; j--){
            for(int i=0; i<matrix.size(); i++){
                if(matrix[i][j] == '0') continue;
                int left = i-1, right = i+1, t = matrix[i][j];
                //matrix[left][j] >= t 此条件保证当前行的上下行的连续1的个数大于当前行
                while(left >= 0 && matrix[left][j] >= t) left--;
                while(right < matrix.size() && matrix[right][j] >= t) right++;
                rt = max(rt, (t-48)*(right-left-1));
            }
        }
        return rt;
    }
};