C++ 中的最大矩形
c++server side programmingprogramming
假设我们有一个二维二元矩阵，其中存在 0 和 1。我们需要找到仅包含 1 的最大矩形并返回其面积。
为了解决这个问题，我们将遵循以下步骤−
定义一个名为 getAns 的函数，该函数接收数组 a
创建堆栈 st，i := 0，ans := 0
while i < a 的大小，则
如果栈为空或 a[i] >= 栈顶，则将 i 插入栈中，并将 i 加 1
否则减
高度 := a[栈顶]，从栈中删除
当栈为空时，宽度 := i，否则 i – 栈顶 – 1
面积 := 高度 * 宽度
ans := ans 和面积的最大值
当 st 不为空时
height := a[st 的顶部]，从堆栈中删除
当 st 为空时，width := a 的大小，否则为 a 的大小 – st 的顶部 – 1
面积 := 高度 * 宽度
ans := ans 和面积的最大值
返回 ans
在主方法中执行以下操作 −
ans := 0, n := x 的大小
如果 n 为零，则返回 0
m := x[0] 的大小
创建一个高度为 m 的数组
i 在 0 到 n 的范围内 – 1
j 在 0 到 m 的范围内 – 1
如果 x[i, j] = 1，则 height[j] 增加 1，否则 height[j] := 0
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
