पायथन में हिस्टोग्राम के तहत सबसे बड़ा आयत क्षेत्र खोजने का कार्यक्रम

मान लीजिए कि हमारे पास हिस्टोग्राम में बार की ऊंचाई का प्रतिनिधित्व करने वाली संख्याओं की एक सूची है। हमें सबसे बड़े आयत का क्षेत्रफल ज्ञात करना है जो कि सलाखों के नीचे बन सकता है।

इसलिए, यदि इनपुट अंकों की तरह है =[3, 2, 5, 7]

तो आउटपुट 10

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

• stk :=एक स्टैक और शुरू में इसमें -1 डालें
• ऊंचाई के अंत में 0 डालें
• उत्तर:=0
• i के लिए 0 से लेकर ऊंचाई के आकार तक, करें
  • जबकि ऊंचाई[i] <ऊंचाई[stk के शीर्ष], करते हैं
    • h :=ऊंचाई [stk के ऊपर] और stk से पॉप
    • w :=i - stk के ऊपर - 1
    • उत्तर:=अधिकतम उत्तर और (एच * डब्ल्यू)
  • मुझे stk में धकेलें
• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution:
   def solve(self, heights):
      stk = [-1]
      heights.append(0)
      ans = 0
      for i in range(len(heights)):
         while heights[i] < heights[stk[-1]]:
            h = heights[stk.pop()]
            w = i - stk[-1] - 1
            ans = max(ans, h * w)
         stk.append(i)
      return ans

ob = Solution()
nums = [3, 2, 5, 7]
print(ob.solve(nums))

इनपुट

[3, 2, 5, 7]

आउटपुट

10