给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] 输出: 6代码：
// 动态规划的思想 int MaximumRectangle(const vector<vector<char>> &matrix) { if (matrix.empty()) return 0; int len_x = matrix[0].size(); int len_y = matrix.size(); vector<int> height(len_x, 0); vector<int> left(len_x, 0); vector<int> right(len_x, len_x); // max erea int max_erea = 0; for (int i = 0; i < len_y; i++) { // if matrix[i][j] == 1 new_height[j] = old_height[j] + 1 // else new_height[j] = 0 for (int j = 0; j < len_x; j++) { if (matrix[i][j] == '1') { height[j] = height[j] + 1; } else { height[j] = 0; } } // new_left[j] = max(old_left[j], cur_left) // cur_left是从左遍历 int cur_left = 0; for (int j = 0; j < len_x; j++) { if(matrix[i][j] == '1') left[j] = max(left[j], cur_left); else { left[j] = 0; cur_left = j + 1; } } // new_right[j] = min(old_right[j], cur_right) // cur_right 从右遍历 int cur_right = len_x; for (int j = len_x - 1; j >= 0; j--) { if(matrix[i][j] == '1') right[j] = min(right[j], cur_right); else { // 这里的意思哦 right[j] = len_x; cur_right = j; } } int tmp_erea = 0; for (int j = 0; j < len_x; j++) { tmp_erea = (right[j] - left[j]) * height[j]; if (tmp_erea > max_erea) max_erea = tmp_erea; } } return max_erea; } int main(int argc, char* argv[]) { vector<vector<char>> matrix = { {'1', '0', '1', '1', '0', '0', '1'}, {'0', '1', '1', '1', '1', '0', '1'}, {'1', '0', '1', '1', '0', '0', '1'}, {'1', '0', '1', '0', '1', '1', '1'}, {'1', '0', '0', '1', '1', '1', '1'}, {'0', '0', '1', '1', '0', '0', '1'}, {'0', '0', '1', '0', '0', '0', '1'}, }; int max_erea = MaximumRectangle(matrix); return 0; }
