[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.

思路

对于上图的一个01矩阵。我们可以一行一行的分析，假设第三行，我们按列扫描，遇到0时，柱子断开，重新形成柱子，遇到1时柱子高度加一。这样的话，我们就可以把问题转换为[LeetCode]*84.Largest Rectangle in Histogram求解最大矩形面积。

代码<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjwvcD4NCjxwcmUgY2xhc3M9"brush:java;"> /*--------------------------------------- * 日期：2015-05-14 * 作者：SJF0115 * 题目: 85.Maximal Rectangle * 网址：https://leetcode.com/problems/maximal-rectangle/ * 结果：AC * 来源：LeetCode * 博客： -----------------------------------------*/ #include #include #include using namespace std; class Solution { public: int maximalRectangle(vector >& matrix) { int row = matrix.size(); if(row == 0){ return 0; }//if int col = matrix[0].size(); vector > height(row,vector (col,0)); // 计算每一行的高度 int h; for(int j = 0;j < col;++j){ h = 0; for(int i = 0;i < row;++i){ if(matrix[i][j] == '1'){ ++h; }//if else{ h = 0; }//else height[i][j] = h; }//for }//for /*for(int i = 0;i < row;++i){ for(int j = 0;j < col;++j){ cout<

运行时间