这道题把二维图转换成行数个的柱状图题，就简单了
1 class Solution { 2 public: 3 int maximalRectangle(vector<vector<char> > &matrix) { 4 int x = matrix.size(); 5 if(0 == x) return 0; 6 int y = matrix[0].size(); 7 if(0 == y) return 0; 8 vector<vector<int> > result(x, vector<int>(y)); 9 for(int i = 0; i < x; ++i) 10 for(int j = 0; j < y; ++j) 11 result[i][j] = '0' == matrix[i][j]? 0: 1; 12 for(int i = 1; i < x; ++i) 13 for(int j = 0; j < y; ++j) 14 result[i][j] += 0 == result[i][j]? 0: result[i-1][j]; 15 int ret = 0; 16 for(int i = 0; i < x; ++i) 17 ret = max(ret, maxArea(result[i])); 18 return ret; 19 } 20 21 int maxArea(vector<int>& line) 22 { 23 stack<int> S; 24 line.push_back(0); 25 int sum = 0; 26 for (int i = 0; i < line.size(); i++) { 27 if (S.empty() || line[i] > line[S.top()]) S.push(i); 28 else { 29 int tmp = S.top(); 30 S.pop(); 31 sum = max(sum, line[tmp]*(S.empty()? i : i-S.top()-1)); 32 i--; 33 } 34 } 35 return sum; 36 } 37 };
C#
1 public class Solution { 2 public int MaximalRectangle(char[,] matrix) { 3 int m = matrix.GetLength(0); 4 int n = matrix.GetLength(1); 5 if (m == 0 || n == 0) return 0; 6 int[,] result = new int[m, n]; 7 for (int i = 0; i < m; i++) { 8 for (int j = 0; j < n; j++) { 9 result[i, j] = '0' == matrix[i, j]? 0 : 1; 10 } 11 } 12 for (int i = 1; i < m; i++) { 13 for (int j = 0; j < n; j++) { 14 result[i, j] += 0 == result[i, j]? 0 : result[i-1, j]; 15 } 16 } 17 int ans = 0; 18 for (int i = 0; i < m; i++) { 19 ans = Math.Max(ans, maxArea(result, i)); 20 } 21 return ans; 22 } 23 public int maxArea(int[,] result, int line) { 24 Stack<int> S = new Stack<int>(); 25 List<int> lineCopy = new List<int>(); 26 for (int i = 0; i < result.GetLength(1); i++) lineCopy.Add(result[line, i]); 27 lineCopy.Add(0); 28 int sum = 0; 29 for (int i = 0; i < lineCopy.Count; i++) { 30 if (S.Count == 0 || lineCopy[i] > lineCopy[S.Peek()]) S.Push(i); 31 else { 32 int peek = S.Peek(); 33 S.Pop(); 34 sum = Math.Max(sum, lineCopy[peek] * (S.Count == 0? i : i - S.Peek() - 1)); 35 i--; 36 } 37 } 38 return sum; 39 } 40 }