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 [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

范例（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