数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ 中的最大矩形
假设我们有一个二维二进制矩阵，其中存在 0 和 1 值。我们必须找到仅包含 1 的最大矩形并返回其面积。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为 getAns 的函数，它将接收数组 a
创建堆栈 st，i := 0，ans := 0
当 i < a 的大小，则
如果堆栈为空或 a[i] >= 堆栈顶部，则将 i 插入 st，i 加 1
否则：
height := a[堆栈顶部]，从堆栈中删除
width := 堆栈为空时的 i，否则为 i – 堆栈顶部 – 1
area := height * width
ans := ans 和 area 的最大值
当 st 不为空时
height := a[st 的顶部]，从堆栈中删除
width := st 为空时的 a 的大小，否则为 a 的大小 – st 的顶部 – 1
area := height * width
ans := ans 和 area 的最大值
返回 ans
从主方法执行以下操作：
ans := 0，n := x 的大小
如果 n 为零，则返回 0
m := x[0] 的大小
创建一个大小为 m 的数组 height
对于 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
更新于：2020年5月26日
325 次浏览
广告