题目描述
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Example1:
Input: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] Output: 6
解题思路
- 跟84题 递增栈是一道题
-
只需要将每一次的保存的列的值传给84题就可以了
- 84题可参考这个：
- 参考
- 维护一个递增的栈，这个栈保存了元素在数组中的位置。
- 这样在栈中每一个左边的bar都比本身小，所以左边就天然有界了，也就是左边界就是左边的一个bar。
- 遍历一遍height数组，在将height数组入栈的时候，如果当前元素height[i]比栈顶元素小，则我们又找到了栈顶元素的右边界。
- 因此我们在此时就可以计算以栈顶元素为最低bar的矩形面积了，因为左右边界我们都已经找到了，而且是在O(1)的时间复杂度内找到的。
- 然后就可以将栈顶元素出栈了。
- 这样每出栈一个元素，即计算以此元素为最低点的矩形面积。当最终栈空的时候我们就计算出了以所有bar为最低点的矩形面积。
- 为保证让所有元素都出栈，我们在height数组最后加一个0，因为一个元素要出栈必须要遇到一个比他小的元素，也就是右边界。
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int res = 0;
vector<int> height;
int row = matrix.size();
if(row == 0){
return 0;
}
int col = matrix[0].size();
for(int i = 0; i < row; i++){
height.resize(col);
for(int j = 0; j < col; j++){
height[j] = matrix[i][j] == '0' ? 0 : (1 + height[j]);
}
res = max(res, largestRectangleArea(height));
}
return res;
}
int largestRectangleArea(vector<int>& heights) {
if(heights.size() == 0){
return 0;
}
heights.push_back(0);
int size = heights.size();
int res = 0;
stack<int> s;
for(int i = 0; i < size; i++){
while(!s.empty() && heights[i] < heights[s.top()]){
auto val = s.top();
s.pop();
res = max(res, heights[val] * (i - 1 - (s.empty() ? -1 : s.top())));
}
s.push(i);
}
return res;
}
};
