[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求解最大矩形面积。

代码

/*—————————————* 日期：2015-05-14* 作者：SJF0115* 题目: 85.Maximal Rectangle* 网址：https://leetcode.com/problems/maximal-rectangle/* 结果：AC* 来源：LeetCode* 博客：—————————————–*/;class Solution {public:int maximalRectangle(vector<vector<char>>& matrix) {int row = matrix.size();if(row == 0){return 0;}//ifint col = matrix[0].size();vector<vector<int> > height(row,vector<int>(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;}//ifelse{h = 0;}//elseheight[i][j] = h;}//for}//for/*for(int i = 0;i < row;++i){for(int j = 0;j < col;++j){cout<<height[i][j]<<” “;}cout<<endl;}//for*/// 计算以第i行为底的矩形面积int maxArea = 0;for(int i = 0;i < row;++i){maxArea = max(maxArea,MaxRectangle(height[i]));}//forreturn maxArea;}private:int MaxRectangle(vector<int> height){int size = height.size();if(size == 0){return 0;}//ifint maxArea = 0;stack<int> indexStack;int top,width;for(int i = 0;i < size;++i){if(indexStack.empty() || height[i] >= height[indexStack.top()]){indexStack.push(i);}//ifelse{top = indexStack.top();indexStack.pop();width = indexStack.empty() ? i : (i – indexStack.top() – 1);maxArea = max(maxArea,height[top] * width);–i;}//else}//forwhile(!indexStack.empty()){top = indexStack.top();indexStack.pop();width = indexStack.empty() ? size : (size – indexStack.top() – 1);maxArea = max(maxArea,height[top] * width);}//whilereturn maxArea;}};int main(){Solution s;vector<vector<char> > matrix = {{‘0′,’1′,’0′,’1′,’1’},{‘1′,’1′,’1′,’0′,’0’},{‘1′,’1′,’1′,’1′,’0’},{‘1′,’0′,’1′,’1′,’1’},{‘0′,’1′,’0′,’0′,’0’}};cout<<s.maximalRectangle(matrix)<<endl;return 0;}

运行时间

正确的寒暄必须在短短一句话中明显地表露出你对他的关怀。