सी++ में अधिकतम आयत

मान लीजिए कि हमारे पास 2 डी बाइनरी मैट्रिक्स है जहां 0 और 1 मान मौजूद हैं। हमें केवल 1s वाला सबसे बड़ा आयत खोजना है और उसका क्षेत्रफल वापस करना है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे-

• getAns नामक एक फ़ंक्शन को परिभाषित करें, यह एक सरणी लेगा

• स्टैक सेंट बनाएं, i:=0, उत्तर:=0

• जबकि मैं <आकार a, तब

  • यदि स्टैक खाली है या a[i]>=स्टैक के ऊपर, तो i को st में डालें, i को 1 से बढ़ाएँ

  • अन्यथा -

    • ऊंचाई:=ए [स्टैक का शीर्ष], स्टैक से हटाएं

    • चौड़ाई :=i जब स्टैक खाली हो, अन्यथा i – सेंट के ऊपर – 1

    • क्षेत्र:=ऊंचाई * चौड़ाई

    • उत्तर :=अधिकतम उत्तर और क्षेत्रफल

• जबकि सेंट खाली नहीं है

  • ऊंचाई:=ए [सेंट का शीर्ष], स्टैक से हटाएं

  • चौड़ाई :=एक का आकार जब सेंट खाली है, अन्यथा ए का आकार – सेंट के शीर्ष – 1

  • क्षेत्र:=ऊंचाई * चौड़ाई

  • उत्तर :=अधिकतम उत्तर और क्षेत्रफल

• वापसी उत्तर

• मुख्य विधि से निम्न कार्य करें -

• उत्तर:=0, एन:=x का आकार

• अगर n शून्य है, तो वापस 0

• मी :=x का आकार[0]

• मी आकार की एक सरणी ऊंचाई बनाएं

• मेरे लिए 0 से n - 1 की सीमा में

  • j के लिए 0 से m - 1 की सीमा में

    • यदि x[i, j] =1, तो ऊँचाई [j] 1 से बढ़ाएँ, अन्यथा ऊँचाई [j] :=0

  • उत्तर:=अधिकतम उत्तर और प्राप्त उत्तर (ऊंचाई)

• वापसी उत्तर

उदाहरण (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