यह एक C++ प्रोग्राम है जो हिस्टोग्राम में सबसे बड़ा आयताकार क्षेत्र ज्ञात करता है।
फंक्शन getArea() का एल्गोरिदम:
Begin एक खाली स्टैक बनाएं। largest_area इनिशियलाइज़ करें। पहले बार से शुरू करके हर बार hist[i] के लिए एक व्हाइल लूप करें, जहां i = 0 से n से कम: यदि स्टैक खाली है या hist[i] स्टैक के शीर्ष पर बार से अधिक ऊंचा है, तो 'i' को स्टैक में पुश करें। अन्यथा यह बार स्टैक के शीर्ष से छोटा है, तो तब तक स्टैक के शीर्ष को हटाते रहें जब तक स्टैक का शीर्ष अधिक है। सबसे छोटे बार के साथ आयत का क्षेत्रफल ज्ञात करें। स्टैक में शीर्ष से पहले का एलिमेंट बाएं इंडेक्स के लिए है और i शीर्ष के लिए दाएं इंडेक्स है। यदि स्टैक खाली नहीं है तो स्टैक से शेष बार को पॉप करें और प्रत्येक पॉप किए गए बार को सबसे छोटे बार के रूप में क्षेत्रफल की गणना करें। End
उदाहरण कोड
#include<iostream> #include<stack> using namespace std; int getArea(int hist[], int n) { stack<int> st; int largest_area = 0; int top; int toparea; int i = 0; while (i < n) { if (st.empty() || hist[st.top()] <= hist[i]) st.push(i++); else { top = st.top(); st.pop(); toparea = hist[top] * (st.empty() ? i : i - st.top() - 1); if (largest_area < toparea) largest_area = toparea; } } while (st.empty() == false) { top = st.top(); st.pop(); toparea = hist[top] * (st.empty() ? i : i - st.top() - 1); if (largest_area < toparea) largest_area = toparea; } return largest_area; } int main() { int hist[] = {6,7,4,5,3,2}; int n = sizeof(hist)/sizeof(hist[0]); cout << "Largest area is " << getArea(hist, n); return 0; }
आउटपुट
Largest area is 16
