Here is the idea: (refer from http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html)

- For each row, compute the continuous '1' number which is adjacent above.
- For each row, apply the max adjacent rectangle area to compute.
- The largest one is the result.

Question: It looks there is one-off error. Can you see it?

Submission Result: Wrong Answer

Input: ["01101","11010","01110","11110","11111","00000"]

Output: 8

Expected: 9

```
class Solution { public:
int maximalRectangle(vector<vector<char> > &matrix) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int maxArea = 0;
if (matrix.size() == 0) return 0;
vector<int> hist(matrix[0].size(),0);
for (int row=0; row< matrix.size(); row++)
{
//compute hist.
for (int col=0; col<matrix[0].size();col++)
{
if (matrix[row][col] == '0') {
hist[col] = 0;
}else{
hist[col] += 1;
}
}
//get max history rectangle size
maxArea = max(maxArea, maxRectHistArea(matrix, hist));
}
return maxArea;
}
private:
int maxRectHistArea(vector<vector<char> > &matrix, vector<int> &hist)
{
stack<int> S; //store array index;
int maxArea = INT_MIN;
for (int i=0; i<hist.size(); i++)
{
if (S.empty()) {
S.push(i);
continue;
}
while(!S.empty() && hist[S.top()] > hist[i]) {
int index = S.top();
S.pop();
int area = (i - index)*hist[index];
if (area > maxArea) maxArea = area;
}
S.push(i);
}
//clean stack
while(!S.empty()){
int area = (hist.size() - S.top())*hist[S.top()];
if (area > maxArea) maxArea = area;
S.pop();
}
return maxArea;
} };
```

Figure out the root cause. We have to save both index and height information into stack somehow. Here is working one.

```
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int maxArea = 0;
if (matrix.size() == 0) return 0;
vector<int> hist(matrix[0].size(),0);
for (int row=0; row< matrix.size(); row++)
{
//compute hist.
for (int col=0; col<matrix[0].size();col++)
{
if (matrix[row][col] == '0') {
hist[col] = 0;
}else{
hist[col] += 1;
}
}
//get max hist rectangle area
maxArea = max(maxArea, largestRectangleArea(hist));
}
return maxArea;
}
public:
struct Item{
int index;
int height;
Item(int i,int h):index(i),height(h){};
Item():index(-1),height(0){};
};
private:
int largestRectangleArea(vector<int> &height) {
stack<Item> S;
int N = height.size();
int area = 0;
for (int i=0; i<N; i++)
{
if (S.empty()) {
S.push(Item(i,height[i]));
continue;
}
//compare
if (height[i] < S.top().height){
//pop till empty or smaller item appear
Item item;
while (!S.empty() && S.top().height > height[i]) {
item = S.top();
S.pop();
area = max(area, (i - item.index)*item.height);
}
//push. Pay attention to the index
S.push(Item(item.index, height[i]));
}else{
S.push(Item(i,height[i]));
}
}
//stack maybe not empty yet
while(!S.empty()){
Item item = S.top(); S.pop();
area = max(area, (N - item.index)*item.height);
}
return area;
}
};
```