C ++中的最大矩形
假设我们有一个二维二进制矩阵，其中存在0和1值。我们必须找到仅包含1的最大矩形，并返回其面积。
为了解决这个问题，我们将按照以下步骤操作：
定义一个名为getAns的函数，它将使用数组a
创建堆栈st，i：=0，ans：=0
当我<a的大小时
height：=a[堆栈顶部]，从堆栈中删除
宽度：=i，当堆栈为空时，否则i–st的顶部–1
面积：=高度*宽度
ans：=ans和area的最大值
如果堆栈为空或a[i]>=堆栈顶部，则将i插入st，将i增加1
否则-
当st不为空时
height：=a[stoftop]，从堆栈中删除
宽度：=当st为空时的大小，否则为–st的顶部–1
面积：=高度*宽度
ans：=ans和area的最大值
返回ans
从主要方法中执行以下操作-
ans：=0，n：=x的大小
如果n为零，则返回0
m：=x[0]的大小
创建一个大小为m的数组高度
对于i，范围为0至n–1
如果x[i，j]=1，则将height[j]加1，否则，height[j]：=0
对于j，范围从0到m–1
ans：=ans和getAns(height)的最大值
返回ans
范例（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int getAns(vector <int> a){
stack <int> st;
int i = 0;
int ans = 0;
while(i<a.size()){
if(st.empty()||a[i]>=a[st.top()]){
st.push(i);
i++;
} else{
int height = a[st.top()];
st.pop();
int width = st.empty()?i:i-st.top()-1;
int area = height * width;
ans = max(ans,area);
}
}
while(!st.empty()){
int height = a[st.top()];
st.pop();
int width = st.empty()?a.size():a.size() - st.top()-1;
int area = height * width;
ans = max(ans,area);
}
return ans;
}
int maximalRectangle(vector<vector<char>>& x) {
int ans = 0;
int n = x.size();
if(!n)return 0;
int m = x[0].size();
vector <int> height(m);;
for(int i =0;i<n;i++){
for(int j =0;j<m;j++){
if(x[i][j] == '1')height[j]++;
else height[j] = 0;
}
ans = max(ans, getAns(height));
}
return ans;
}
};
main(){
vector<vector<char>> v = {
{'1','0','1','0','0'},
{'1','0','1','1','1'},
{'1','1','1','1','1'},
{'1','0','0','1','0'}
};
Solution ob;
cout << (ob.maximalRectangle(v));
}输入值
{{'1','0','1','0','0'},
{'1','0','1','1','1'},
{'1','1','1','1','1'},
{'1','0','0','1','0'}
}输出结果
6