สี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดในฮิสโตแกรมใน Python

สมมติว่าเรามีอาร์เรย์จำนวนเต็มหนึ่งชุดที่แสดงความสูงของฮิสโตแกรม แต่ละแถบมีความกว้างของหน่วย เราต้องหาสี่เหลี่ยมพื้นที่ที่ใหญ่ที่สุดดังนี้ −

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้าง stack ตั้งค่า i :=0, ans :=0

• ในขณะที่ฉัน <ขนาดความสูง แล้ว

  • ถ้า stack มี 0 องค์ประกอบหรือความสูงของ stack top element <=height[i] แล้ว

    • ใส่ i ลงใน stack เพิ่ม i ขึ้น 1

  • มิฉะนั้น −

    • x :=stack top element ลบออกจาก stack

    • ความสูง :=ความสูง[x]

    • temp :=height * (i * stack[-1] – 1) เมื่อ stack ไม่ว่างเปล่า มิฉะนั้น temp :=height * i

    • ans :=สูงสุดของ ans และ temp

• ในขณะที่สแต็กไม่ว่างเปล่า -

  • x :=สแต็คองค์ประกอบด้านบน

  • height :=height[x], ลบออกจาก stack

  • temp :=height * length of heights – stack top element – ​​1 when stack is notempty, มิฉะนั้น temp :=length of heights

  • ans :=สูงสุดของ ans และ 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