পাইথনে হিস্টোগ্রামে সবচেয়ে বড় আয়তক্ষেত্র

ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে আছে যা একটি হিস্টোগ্রামের উচ্চতাকে প্রতিনিধিত্ব করছে। প্রতিটি বার একক প্রস্থ আছে. আমাদের সবচেয়ে বড় আয়তক্ষেত্রটি নিম্নরূপ −

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• স্ট্যাক তৈরি করুন, i :=0, উত্তর :=0

  সেট করুন

• যখন আমি <উচ্চতার আকার, তারপর

  • যদি স্ট্যাকের 0 উপাদান বা স্ট্যাকের শীর্ষ উপাদানের উচ্চতা <=উচ্চতা[i] থাকে, তাহলে

    • স্ট্যাকের মধ্যে i ঢোকান, i বাড়ান 1

  • অন্যথায় -

    • x :=স্ট্যাক শীর্ষ উপাদান, স্ট্যাক থেকে মুছে দিন।

    • উচ্চতা :=উচ্চতা[x]

    • temp :=height * (i * stack[-1] – 1) যখন স্ট্যাক খালি থাকে না অন্যথায় temp :=height * i

    • উত্তর :=সর্বোচ্চ উত্তর এবং তাপমাত্রা

• স্ট্যাক খালি না থাকার সময় −

  • x :=স্ট্যাক শীর্ষ উপাদান

  • উচ্চতা :=উচ্চতা[x], স্ট্যাক থেকে মুছুন

  • temp :=উচ্চতা * উচ্চতার দৈর্ঘ্য – স্ট্যাক টপ এলিমেন্ট – 1 যখন স্ট্যাক নস্ট হয়, অন্যথায় temp :=উচ্চতার দৈর্ঘ্য

  • উত্তর :=সর্বোচ্চ উত্তর এবং তাপমাত্রা

• উত্তর ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

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