C++での最大長方形

0と1の値が存在する2Dバイナリ行列があるとします。 1のみを含む最大の長方形を見つけて、その面積を返す必要があります。

これを解決するために、次の手順に従います-

• getAnsという関数を定義します。これは配列a

  を取ります

• スタックst、i：=0、ans：=0

  を作成します

• i

  • スタックが空の場合、またはa [i]> =スタックの一番上にある場合は、iをstに挿入し、iを1増やします

  • それ以外の場合-

    • height：=a [スタックの一番上]、スタックから削除

    • width：=スタックが空の場合はi、それ以外の場合はi – stの上部– 1

    • 面積：=高さ*幅

    • ans：=ansと面積の最大値

• stが空ではない間

  • height：=a [top of st]、スタックから削除

  • width：=stが空の場合のaのサイズ、それ以外の場合のa – stの上部– 1

  • 面積：=高さ*幅

  • ans：=ansと面積の最大値

• ansを返す

• メインの方法から、次のようにします-

• ans：=0、n：=xのサイズ

• nがゼロの場合、0を返します

• m：=x [0]

  のサイズ

• サイズmの配列の高さを1つ作成します

• 0からn–1の範囲のiの場合

  • 0からm–1の範囲のjの場合

    • 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