假设我们有一个二维二进制矩阵,其中存在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 [st of top],从堆栈中删除
宽度:=当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
让我们看下面的实现以更好地理解-
#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