# Using stack, strengthen the previous problem

• 1.0 Time O(n^2) Space O(n^2)

``````    int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size() == 0)
return 0;
int m = matrix.size(), n = matrix[0].size(), maxArea = 0;
vector<vector<int>> num(m, vector<int>(n + 1, 0));
for(auto i = 0; i < m; i ++)
{
stack<int> s;
for(auto j = 0; j <= n;)
{
if(j != n && matrix[i][j] == '1')
num[i][j] = 1 + (i == 0 ? 0: num[i - 1][j]);
if(s.empty() || num[i][j] >= num[i][s.top()])
s.push(j++);
else
{
int top = s.top();
s.pop();
maxArea = max(maxArea, num[i][top] * (s.empty() ? j: j - s.top() - 1));
}
}
}
return maxArea;
}
``````

1.1 time O(n^2) Space(n)

``````    int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size() == 0)
return 0;
int m = matrix.size(), n = matrix[0].size(), maxArea = 0;
vector<int> num(n + 1, 0);
for(auto i = 0; i < m; i ++)
{
stack<int> s;
bool cur = false;
for(auto j = 0; j <= n;)
{
if(!cur)
if(j != n && matrix[i][j] == '1')
num[j] = 1 + num[j];
else
num[j] = 0;
if(s.empty() || num[j] >= num[s.top()])
{
s.push(j++);
cur = false;
}
else
{
int top = s.top();
s.pop();
maxArea = max(maxArea, num[top] * (s.empty() ? j: j - s.top() - 1));
cur = true;
}
}
}
return maxArea;
}
``````

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