leetCode. 85. 最大矩形
部分参考上一题链接
leetCode.84. 柱状图中最大的矩形
此题思路
代码
class Solution {
public:
int largestRectangleArea( vector<int>& h ) {
int n = h.size();
vector<int> left( n ), right( n );
stack<int> st;
// 求每个矩形的第一个小于左边界的矩形 - 用单调栈
for ( int i = 0; i < n; ++i ) {
while ( st.size() && h[st.top()] >= h[i] ) st.pop();
if ( st.empty() ) left[i] = -1;
else left[i] = st.top();
st.push( i );
}
// 求每个矩形的第一个小于右边界的矩形 - 用单调栈
st = stack<int>(); // 清空栈
for ( int i = n - 1; i >= 0; --i ) {
while ( st.size() && h[st.top()] >= h[i] ) st.pop();
if( st.empty() ) right[i] = n;
else right[i] = st.top();
st.push( i );
}
// 遍历维护 最大值
int ret = 0;
for (int i = 0; i < n; ++i) ret = max( ret, (right[i] - left[i] - 1) * h[i] );
return ret;
}
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
int n = matrix.size(), m = matrix[0].size();// n 行, m 列
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] = 1 + h[i - 1][j];
else h[i][j] = 1;
}
}
}
int ret = 0;
// 把每行的矩形,按照上题的思路进行处理,然后维护最大值就好
for(int i = 0; i < n; i ++) ret = max(ret, largestRectangleArea(h[i]));
return ret;
}
};
标签:size,matrix,int,ret,st,矩形,leetCode,85
From: https://blog.csdn.net/qq_48290779/article/details/139276240