# It seems the testing data is a bit too weak. The following O(n^3) solution got accepted with 16 ms...

• ``````class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (!m) return 0;
int n = matrix[0].size();
if (!n) return 0;

vector<int> h(n+2, 0);
int best = 0;
for (int i = 0 ; i < m ; i++) {
for (int j = 0 ; j < n ; j++)
h[j+1] = matrix[i][j] == '1' ? h[j+1]+1 : 0;
//for (int j = 1 ; j <= n ; j++) cout<<h[j]<<",";
//cout<<endl;

for (int m = 1 ; m <= n ; m++) {
if (h[m] == 0) continue;
int l = m;
while (h[l] >= h[m]) l--;
int r = m;
while (h[r] >= h[m]) r++;
int area = (r - l - 1) * h[m];
if (area > best) best = area;
}
}
return best;
}
};
``````

For comparison, the O(n^2) solution using stack costs 20 ms:

``````class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (!m) return 0;
int n = matrix[0].size();
if (!n) return 0;

vector<int> h(n+2, 0);
int best = 0;
for (int i = 0 ; i < m ; i++) {
for (int j = 0 ; j < n ; j++)
h[j+1] = matrix[i][j] == '1' ? h[j+1]+1 : 0;
//for (int j = 1 ; j <= n ; j++) cout<<h[j]<<",";
//cout<<endl;
stack<int> st;
st.push(0);
for (int r = 1 ; r <= n+1 ; r++) {
int m = st.top();
while (h[m] > h[r]) {
st.pop();
int l = st.top();
int area = (r - l - 1) * h[m];
if (area > best) best = area;
m = l;
}

if (h[r] == h[m]) st.top() = r; else st.push(r);
}

/*
for (int m = 1 ; m <= n ; m++) {
if (h[m] == 0) continue;
int l = m;
while (h[l] >= h[m]) l--;
int r = m;
while (h[r] >= h[m]) r++;
int area = (r - l - 1) * h[m];
if (area > best) best = area;
}*/
}
return best;
}
};``````

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