পাইথনে হিস্টোগ্রামের অধীনে বৃহত্তম আয়তক্ষেত্র এলাকা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে একটি হিস্টোগ্রামে বারের উচ্চতা প্রতিনিধিত্বকারী সংখ্যাগুলির একটি তালিকা রয়েছে। আমাদের সবচেয়ে বড় আয়তক্ষেত্রের ক্ষেত্রফল খুঁজে বের করতে হবে যা বারগুলির নীচে গঠিত হতে পারে৷

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[3, 2, 5, 7]

তাহলে আউটপুট হবে 10

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

• stk :=একটি স্ট্যাক এবং প্রাথমিকভাবে এতে -1 ঢোকান
• উচ্চতার শেষে 0 ঢোকান
• উত্তর :=0
• আমি রেঞ্জ 0 থেকে উচ্চতার আকারের জন্য, করুন
  • যখন উচ্চতা[i]
  • h :=উচ্চতা [stk এর শীর্ষ] এবং stk থেকে পপ
  • w :=i - stk - 1 এর শীর্ষ
  • উত্তর :=সর্বাধিক উত্তর এবং (h * w)
• আমাকে 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