LeetCode 85. 85. 最大矩形
原题链接
困难
作者:
我是java同学
,
2023-10-10 20:59:59
,
所有人可见
,
阅读 54
class Solution {
public:
int get(vector<int> h) {
stack<int> stk;
int n = h.size();
vector<int> l(n), r(n);
for (int i = 0; i < n; i ++ ) {
while (stk.size() && h[stk.top()] > h[i]) stk.pop();
if (stk.empty()) l[i] = -1;
else l[i] = stk.top();
stk.push(i);
}
stk = stack<int>();
for (int i = n - 1; i >= 0; i -- ) {
while (stk.size() && h[stk.top()] >= h[i]) stk.pop();
if (stk.empty()) r[i] = n;
else r[i] = stk.top();
stk.push(i);
}
int res = 0;
for (int i = 0; i < n; i ++ )
res = max(res, (r[i] - l[i] - 1) * h[i]);
return res;
}
int maximalRectangle(vector<vector<char>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> h(n, vector<int>(m));
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (matrix[i][j] == '1') {
if (i) h[i][j] = h[i - 1][j] + 1;
else h[i][j] = 1;
}
int res = 0;
for (int i = 0; i < n; i ++ )
res = max(res, get(h[i]));
return res;
}
};