# It complains error. Can you see what's wrong?

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

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

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

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;
}
};``````

• You need to show that you have done minimal research before asking a question. Please read the FAQ for guidelines on how to ask a question.

• Sorry that I should be more specific. I followed the method http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html

But my implementation seems has a bug there while I can't find it by code review. I didn't use debugger to debug it out because I think it's another way towards interview preparation.