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 = (istack[top1]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;
}
};
Clean yet still beating them all accepted with 8ms in C++


Some comments can be helpful
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 = (istack[top1]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; } };
