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

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

সমাধানের ধাপগুলো −

• স্ট্যাক তৈরি করুন, i := 0, ans := 0
• while i < len(heights) − যদি স্ট্যাক খালি থাকে অথবা heights[stack[-1]] <= heights[i] তবে stack.append(i); i++
• অন্যথায় − x = stack.pop(); height = heights[x]; temp = height * (i - stack[-1] - 1) যদি স্ট্যাক খালি না হয় অন্যথা height * i; ans = max(ans, temp)
• স্ট্যাক খালি না হওয়া পর্যন্ত − x = stack.pop(); height = heights[x]; temp = height * (len(heights) - stack[-1] - 1) যদি স্ট্যাক খালি না হয় অন্যথা height * len(heights); ans = max(ans, temp)
• ans রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন −

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