Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
DP。用f[i][j]来记录i行以j列为结尾，往前连续的1的个数。然后再一个O(n^3)的循环来找以(i, j)为右下角的矩形最大的1的面积。
1 class Solution { 2 private: 3 int f[1000][1000]; 4 public: 5 int maximalRectangle(vector > &matrix) { 6 // Start typing your C/C++ solution below 7 // DO NOT write int main() function 8 for(int i = 0; i < matrix.size(); i++) 9 f[i][0] = matrix[i][0] == '1' ? 1 : 0;10 11 for(int i = 0; i < matrix.size(); i++)12 for(int j = 1; j < matrix[i].size(); j++)13 f[i][j] = matrix[i][j] == '1' ? f[i][j-1] + 1 : 0;14 15 int ret = 0;16 17 for(int i = 0; i < matrix.size(); i++)18 for(int j = 0; j < matrix[i].size(); j++)19 {20 int k = i;21 int width = INT_MAX;22 23 while(k >= 0)24 {25 if (f[k][j] == 0)26 break;27 28 width = min(width, f[k][j]);29 30 ret = max(ret, width * (i - k + 1)); 31 32 k--; 33 }34 }35 36 return ret;37 }38 };
O(n^2)的算法，可以把问题看成求多个直方图的最大矩形面积，这样就可以从上往下来做例如第i层就是0~i的直方图，第i+1就是0~i+1的直方图，这样求直方图的复杂度O(n)，于是就有O(n^2)
1 class Solution { 2 public: 3 int calArea(vector &a, vector &width) 4 { 5 for(int i = 0; i < width.size(); i++) 6 width[i] = 0; 7 8 stack s; 9 for(int i = 0; i < a.size(); i++)10 if (s.empty())11 {12 s.push(i);13 width[i] = 0;14 }15 else16 {17 while(!s.empty())18 {19 if (a[s.top()] < a[i])20 {21 width[i] = i - s.top() - 1;22 s.push(i);23 break;24 }25 else26 s.pop();27 }28 29 if (s.empty())30 {31 s.push(i);32 width[i] = i;33 }34 }35 36 while(!s.empty())37 s.pop();38 39 for(int i = a.size() - 1; i >= 0; i--)40 if (s.empty())41 {42 s.push(i);43 width[i] = 0;44 }45 else46 {47 while(!s.empty())48 {49 if (a[i] > a[s.top()])50 {51 width[i] += s.top() - i - 1;52 s.push(i);53 break;54 }55 else56 s.pop();57 }58 59 if (s.empty())60 {61 width[i] += a.size() - i - 1;62 s.push(i);63 }64 }65 66 int maxArea = 0; 67 for(int i = 0; i < width.size(); i++)68 maxArea = max(maxArea, (width[i] + 1) * a[i]);69 70 return maxArea;71 }72 73 int maximalRectangle(vector > &matrix) {74 // Start typing your C/C++ solution below75 // DO NOT write int main() function76 if (matrix.size() == 0)77 return 0;78 79 vector a(matrix[0].size(), 0);80 vector width(matrix[0].size());81 82 int maxArea = 0;83 for(int i = 0; i < matrix.size(); i++)84 {85 for(int j = 0; j < matrix[i].size(); j++)86 a[j] = matrix[i][j] == '1' ? a[j] + 1 : 0;87 88 maxArea = max(maxArea, calArea(a, width));89 }90 91 return maxArea;92 }93 };