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

สมมติว่าเรามีรายการตัวเลขที่แสดงความสูงของแท่งกราฟในฮิสโตแกรม เราต้องหาพื้นที่ของสี่เหลี่ยมที่ใหญ่ที่สุดที่สามารถเกิดขึ้นได้ภายใต้แท่งไม้

ดังนั้น หากอินพุตเป็น nums =[3, 2, 5, 7]

แล้วผลลัพธ์จะเป็น 10

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

• stk :=สแต็คและเริ่มต้นแทรก -1 เข้าไป
• ใส่ 0 ที่ส่วนท้ายของความสูง
• ตอบ :=0
• สำหรับ i ในช่วง 0 ถึงขนาดของความสูง ทำ
  • ในขณะที่ heights[i]
  • h :=heights[top of stk] และ pop จาก stk
  • w :=i - ด้านบนของ stk - 1
  • ans :=สูงสุดของ ans และ (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