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

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

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

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

• जबकि मैं <ऊंचाई का आकार, तब

  • यदि स्टैक में 0 तत्व या स्टैक शीर्ष तत्व की ऊँचाई <=ऊँचाई [i] है, तो

    • i को स्टैक में डालें, i को 1 से बढ़ाएँ

  • अन्यथा -

    • x:=स्टैक टॉप एलिमेंट, स्टैक से डिलीट करें।

    • ऊँचाई:=ऊँचाई [x]

    • अस्थायी:=ऊंचाई * (i * स्टैक [-1] - 1) जब स्टैक खाली नहीं होता है अन्यथा अस्थायी:=ऊंचाई * i

    • उत्तर:=अधिकतम उत्तर और अस्थायी

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

  • x :=स्टैक टॉप एलिमेंट

  • ऊँचाई:=ऊँचाई [x], स्टैक से हटाएं

  • अस्थायी:=ऊँचाई * ऊँचाई की लंबाई - स्टैक शीर्ष तत्व - 1 जब स्टैक खाली हो, अन्यथा अस्थायी:=ऊँचाई की लंबाई

  • उत्तर:=अधिकतम उत्तर और अस्थायी

• वापसी उत्तर

उदाहरण

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

class Solution(object):
   def largestRectangleArea(self, heights):
      stack = []
      i = 0
      ans = 0
      while i < len(heights):
         if len(stack) == 0 or heights[stack[-1]]<=heights[i]:
            stack.append(i)
            i+=1
         else:
            x = stack[-1]
            stack.pop()
            height = heights[x]
            temp = height * (i-stack[-1]-1) if len(stack)!= 0 else height * i
            ans = max(ans,temp)
      while len(stack)>0:
         x = stack[-1]
         height = heights[x]
         stack.pop()
         temp = height * (len(heights)-stack[-1]-1) if len(stack)!= 0 else height* len(heights)
         ans = max(ans,temp)
      return ans
ob = Solution()
print(ob.largestRectangleArea([2,1,5,7,3,2]))

इनपुट

[2,1,5,7,3,2]

आउटपुट

12