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