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

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

เช่น ถ้าอินพุตเป็น nums = [3, 2, 5, 7]

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

ขั้นตอนการแก้ปัญหา

• stk := สแต็ก ใส่ค่า -1 เข้าไปก่อน
• เพิ่มค่า 0 เข้าไปท้ายของ heights
• ans := 0
• วนลูป i จาก 0 ถึงขนาดของ heights:
  • ในขณะที่ heights[i] < heights[top of stk]:
    • h := heights[top of stk] และนำออกจาก stk
    • w := i - top of stk - 1
    • ans := max(ans, h * w)
  • เพิ่ม i เข้าไปใน stk
• คืนค่า ans

ตัวอย่างโค้ด

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