# Clean yet still beating them all accepted with 8ms in C++

• ``````class Solution {
private:
int getMax(int* heights, int* stack, int size)
{
int cur = 0, max = 0, top = 0;
stack[top] = -1;
for(int i = 0; i < size; ++i)
{
while(top>0 && heights[stack[top]]>heights[i])
{
cur = (i-stack[top-1]-1)*heights[stack[top]];
top--;
if(cur > max) max = cur;
}
stack[++top] = i;
}
return max;
}
public:
int maximalRectangle(vector<vector<char>>& matrix)
{
int rowSize = matrix.size();
if(!rowSize) return 0;
int colSize = matrix[0].size();
int heights[colSize+1]{0}, stack[colSize+1]{0}, largest = 0;
for(int r = 0; r < rowSize; ++r)
{
for(int c = 0; c < colSize; ++c)
matrix[r][c]=='1'? heights[c]++ : heights[c]=0;
largest = max(largest, getMax(heights, stack, colSize+1));
}
return largest;
}
};``````

• This post is deleted!

• This post is deleted!

``````class Solution {
private:
int getLargest(int* heights, int* stack, int size)
{
int current = 0, max = 0, top = 0;
stack[top] = -1; //ensure the width of the area is okay, hitting the bottom of stack;
for(int i = 0; i < size; ++i)
{
while(top>0 && heights[stack[top]]>heights[i]) //keep the stack in ascending order;
{
current = (i-stack[top-1]-1) * heights[stack[top]]; //get the area started with the height indexes by stack[top];
top--;
if(current > max) max = current;
}
stack[++top] = i;
}
return max;
}
public:
int maximalRectangle(vector<vector<char>>& matrix)
{
int rowSize = matrix.size();
if(rowSize == 0) return 0;
int colSize = matrix[0].size();
int heights[colSize+1] = {0}; //spare another column for sentinel so when we finish checking heights, it can automatically collect the leftover in stack;
int stack[colSize+1] = {0}; //stay ascending order to avoid redundant calculation;
int largest = 0;
for(int r = 0; r < rowSize; ++r)
{
for(int c = 0; c < colSize; ++c) matrix[r][c]=='1'? heights[c]++ : heights[c]=0;
largest = max(largest, getLargest(heights, stack, colSize+1));
}
return largest;
}
};``````

• @LHearen Very impressive solution, clean and efficient. Thank you!

• Unbelievable! Beating almost all the others! Great, man!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.