Largest Rectangle in Histogram
Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example 1:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.
class Solution {
public:
int largestHistogram(vector<int>&nums) {
int area,maxarea = 0,i;
stack<int> s;
int n = nums.size();
for(i=0;i<n;) {
if(s.empty()||nums[s.top()]<=nums[i])
s.push(i++);
else
{
while(!s.empty()&&nums[s.top()]>nums[i]) {
int top = s.top();
s.pop();
// cout<<"here";
if(s.empty())
area = nums[top] * i;
else
{
area = nums[top] *(i-s.top()-1);
}
maxarea = max(maxarea,area);
}
}
}
while(!s.empty()) {
int top = s.top();
s.pop();
if(s.empty())
{
area = nums[top] * i;
}
else
area = nums[top] *(i-s.top()-1);
maxarea = max(maxarea,area);
}
return maxarea;
}
int maximalRectangle(vector<vector<char>>& matrix) {
int row = matrix.size();
if(!row)
return 0;
int col = matrix[0].size();
vector<int> temp(col,0);
int maxarea = 0;
for(int i=0;i<row;i++) {
for(int j=0;j<col;j++) {
if(**matrix[i][j]=='0'**)**//take care of the data type of the matrix**
temp[j] = 0;
else
temp[j]+=1;
}
int area = largestHistogram(temp);
// cout<<area;
maxarea = max(area,maxarea);
}
return maxarea;
}
};
// Time Complexity: O(n^2)