# Leetcode 85 Solution

https://leetcode.com/problems/maximal-rectangle

## Solution

``````class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s;

vector<int> a(heights.size());
vector<int> b(heights.size());

for (int i = 0; i < heights.size(); i++)
{
while (s.empty() == false && heights[i] <= heights[s.top()])
s.pop();

a[i] = heights[i] * (s.empty() ? i : (i - 1 - s.top()));
s.push(i);
}

s = stack<int>();
for (int i = heights.size() - 1; i >= 0; i--)
{
while (s.empty() == false && heights[i] <= heights[s.top()])
s.pop();

b[i] = heights[i] * (s.empty() ? (heights.size() - 1 - i) : (s.top() - 1 - i));
s.push(i);
}

int max_val = 0;
for (int i = 0; i < heights.size(); i++)
max_val = max(max_val, a[i] + b[i] + heights[i]);

return max_val;
}

int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0)
return 0;
int n = matrix[0].size();

vector<int> h(n);

int max_val = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
h[j] = (matrix[i][j] == '0' ? 0 : h[j] + 1);

int val = largestRectangleArea(h);
max_val = max(val, max_val);
}

return max_val;
}
};
``````