ধরুন আমাদের কাছে একটি 2D বাইনারি ম্যাট্রিক্স আছে যেখানে 0 এবং 1 রয়েছে। আমাদের কাজ হল শুধু 1 ধারণ করা সবচেয়ে বড় আয়তাকার অঞ্চল খুঁজে বের করা এবং তার এলাকা রিটার্ন করা।
সমাধানের পদ্ধতি:
getAns নামে একটি ফাংশন সংজ্ঞায়িত করুন যা একটি অ্যারে a গ্রহণ করবে।
একটি স্ট্যাক st, i := 0, ans := 0 তৈরি করুন।
যখন i < a.size() হয়:
যদি স্ট্যাক খালি থাকে বা a[i] >= a[st.top()], তবে st-এ i পুশ করুন এবং i বাড়ান।
অন্যথায়: height = a[st.top()], স্ট্যাক থেকে পপ করুন। width = i (যদি স্ট্যাক খালি থাকে) অন্যথায় i - st.top() - 1। area = height * width। ans = max(ans, area)।
স্ট্যাক খালি না হওয়া পর্যন্ত: height = a[st.top()], পপ করুন। width = a.size() (স্ট্যাক খালি হলে) অন্যথায় a.size() - st.top() - 1। area = height * width। ans = max(ans, area)।
ans রিটার্ন করুন।
মূল ফাংশন থেকে: ans := 0, n := x.size()। যদি n=0 হয় তবে 0 রিটার্ন করুন। m := x[0].size()। height নামের m আকারের অ্যারে তৈরি করুন।
প্রতিটি রো i-এর জন্য: প্রতিটি কলাম j-এর জন্য, যদি x[i][j] == '1' হয় তবে height[j]++, অন্যথায় height[j] = 0। ans = max(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));
return 0;
}
ইনপুট
{{'1','0','1','0','0'}, {'1','0','1','1','1'}, {'1','1','1','1','1'}, {'1','0','0','1','0'} }
আউটপুট
6
