题目
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.
思路
我自己的解法复杂度非常高，参考别人的dp做法，感觉非常之巧妙啊！！之所以可以用Dp做，是将矩阵的每一个点都用三个变量来刻画它，分别是left（i，j），right（i，j）和height（i，j）。
height（i，j）表示的是（i，j）这个点的当前高度，如果（i，j）这个位置是‘1’，那么它的高度自然由它的上一行的高度来决定，即等于height（i-1，j）+1。如果（i，，j）是‘0’，那height（i，j）就是0
left（i，j）表示的是囊括（i，j）点的矩形的左边边界坐标。有点绕，但是也不难理解，同样如果（i，j）=‘1’，那么left(i,j) = max(left(i-1,j), curleft), curleft 是当前行的左边界，也就是由上一行和当前行的左边界最大值决定。
right（i，j）类似left，只不过是取最小值。
最后计算面积时，只需要将每个点的（height*（right-left））即可。
代码
@author：monkeyduck@2015.3.22@link：http://blog.csdn.net/monkeyduckclass Solution {public:int maximalRectangle(vector<vector<char> > &matrix) {if (matrix.empty()) return 0;const int m = matrix.size();const int n = matrix[0].size();int left[n],right[n],height[n];fill_n(left,n,0);fill_n(right,n,n);fill_n(height,n,0);int maxArea = 0;for (int i=0;i<m;i++){int curleft=0;int curright=n;for (int j=0;j<n;j++){if (matrix[i][j]==’1′){height[j]++;}else{height[j]=0;}}for (int j=0;j<n;j++){//from left to rightif (matrix[i][j]==’1′){left[j]=left[j]>curleft?left[j]:curleft;}else{left[j]=0;curleft=j+1;}}for (int j=n-1;j>=0;j–){if (matrix[i][j]==’1′){right[j]=right[j]<curright?right[j]:curright;}else{right[j]=n;curright=j;}}for (int j=0;j<n;j++){maxArea = height[j]*(right[j]-left[j])>maxArea? height[j]*(right[j]-left[j]):maxArea;}}return maxArea;}};
转载请注明出处
积极思考造成积极人生，消极思考造成消极人生。
