C++ में मैक्सिमल रेक्टेंगल

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

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• getAns नामक एक फ़ंक्शन परिभाषित करें, जो ऐरे a लेता है।
• स्टैक st बनाएं, i := 0, ans := 0
• जब तक i < a का आकार:
  • यदि स्टैक खाली है या a[i] >= स्टैक के शीर्ष, तो i को st में डालें, i को 1 बढ़ाएं
  • अन्यथा:
    • height := a[स्टैक का शीर्ष], स्टैक से हटाएं
    • width := i जब स्टैक खाली हो, अन्यथा i - स्टैक का शीर्ष - 1
    • area := height * width
    • ans := ans और area का अधिकतम
• जब तक st खाली नहीं है:
  • height := a[st का शीर्ष], स्टैक से हटाएं
  • width := a का आकार जब st खाली हो, अन्यथा a का आकार - st का शीर्ष - 1
  • area := height * width
  • ans := ans और area का अधिकतम
• ans वापस करें
• मुख्य विधि से:
  • ans := 0, n := x का आकार
  • यदि n शून्य है, तो 0 वापस करें
  • m := x[0] का आकार
  • आकार m का एक ऐरे height बनाएं
  • i को 0 से n-1 तक लूप चलाएं:
    • j को 0 से m-1 तक लूप चलाएं:
      • यदि 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; 
    } 
}; 
int 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