1 #include <iostream> 2 #include <vector> 3 #include <stack> 4 #include <algorithm> 5 using namespace std; 6  7 class Solution { 8 public: 9     int largestRectangleArea(vector<int> &height) {10         height.push_back(0);11         int i = 0;12         int result = 0;13         stack<int> s;14         while (i < height.size())15         {16             if (s.empty() || height[i]>height[s.top()])17                 s.push(i++);18             else19             {20                 int tmp = s.top();21                 s.pop();22                 result = max(result, height[tmp] * (s.empty() ? i : i - s.top() - 1));23             }24         }25         return result;26     }27 28     int maximalRectangle(vector<vector<char> > &matrix) {29         if (matrix.size() == 0 || matrix[0].size() == 0) return 0;30         int H = matrix.size(), W = matrix[0].size();31         int ret = 0;32 33         int **tmpHeight = new int*[H];34         for (int i = 0; i < H; i++)35         {36             tmpHeight[i] = new int[W];37         }38 39         for (int i = 0; i < H; i++)40         {41             for (int j = 0; j < W; j++)42             {43                 if (matrix[i][j] == ‘0‘)44                 {45                     tmpHeight[i][j] = 0;46                 }47                 else48                 {49 50                     tmpHeight[i][j] = (i == 0 ? 1 : tmpHeight[i - 1][j] + 1);51                 }52             }53         }54         for (int i = 0; i < H; i++)55         {56             vector<int> vtmp(tmpHeight[i], tmpHeight[i] + W);57             ret = max(ret, largestRectangleArea(vtmp));58         }59         return ret;60     }61 };62 63 int main()64 {65     vector<vector<char>> v;66 67     char a1[] = { ‘0‘, ‘1‘, ‘0‘, ‘1‘, ‘1‘};68     char a2[] = { ‘0‘, ‘1‘, ‘1‘, ‘1‘, ‘0‘ };//要用‘1‘和‘0‘来赋值！因为是char数组！不能用1,0 !69     char a3[] = { ‘1‘, ‘1‘, ‘1‘, ‘1‘,‘1‘ };70     v.push_back(vector<char>(a1, a1 + 5));71     v.push_back(vector<char>(a2, a2 + 5));72     v.push_back(vector<char>(a3, a3 + 5));73     Solution s;74     cout << s.maximalRectangle(v) << endl;75     return 0;76     }