给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
以每一行为底，求柱状图中的最大矩形
柱状图中的最大矩形
class Solution {
public:
int largestRectangleArea(vector<int>& h) {
int n = h.size();
int sz = 0;
const int inf = 1e5 + 10;
int stk[n + 1], pre[n + 1], nx[n + 1];
for (int i = 0; i < n; i++) {
while (sz && h[i] <= h[stk[sz]]) {
pre[stk[sz--]] = (sz == 1 ? -1 : stk[sz - 1]);
}
stk[++sz] = i;
}
while (sz >= 1) {
pre[stk[sz--]] = (sz == 1 ? -1 : stk[sz - 1]);
}
sz = 0;
for (int i = 0; i < n; i++) {
while (sz && h[i] < h[stk[sz]]) {
nx[stk[sz--]] = i;
}
stk[++sz] = i;
}
while (sz >= 1) {
nx[stk[sz--]] = n;
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans,(nx[i] - pre[i] - 1)*h[i]);
}
return ans;
}
int maximalRectangle(vector<vector<char>>& M) {
int n = M.size(), m = M[0].size();
vector<int> a(m,0);
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (M[i][j] == '0') a[j] = 0;
else a[j]++;
}
ans = max(ans,largestRectangleArea(a));
}
return ans;
}
};