今天终于来做这题了
昨天写了84题,据说这题就是84的原理,一看,果然是,在84题的代码基础上外面套个for循环就解决了,仍然是用了单调栈哦
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) {
return 0;
}
int n = matrix[0].size();
int ret=0;
vector<vector<int>> heights(m,vector<int>(n));//一个二维数组
for(int i=0;i<n;i++){
heights[0][i]=matrix[0][i]-'0';
}
for(int i=1;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='0'){
heights[i][j]=0;
}
else{
heights[i][j]=heights[i-1][j]+1;
}
}
}
for(int k=0;k<m;k++){
stack<int>st;
int newHeights[n+2];
newHeights[0] = 0;
newHeights[n+1] = 0;
for (int i = 1; i < n+ 1; i++) {
newHeights[i] = heights[k][i - 1];
}
// 开始遍历
for (int i = 0;i<n+2; i++) {
// 如果栈不为空且当前考察的元素值小于栈顶元素值,
// 则表示以栈顶元素值为高的矩形面积可以确定
while (!st.empty() && newHeights[i] < newHeights[st.top()]) {
// 弹出栈顶元素
int cur=st.top();
st.pop();
// 获取栈顶元素对应的高
int curHeight = newHeights[cur];
// 栈顶元素弹出后,新的栈顶元素就是其左侧边界
int leftIndex = st.top();
// 右侧边界是当前考察的索引
int rightIndex = i;
// 计算矩形宽度
int curWidth = rightIndex - leftIndex - 1;
ret =max(ret, curWidth * curHeight);
}
// 当前考察索引入栈
st.push(i);
}
}
return ret;
}
};