Chương trình tìm diện tích hình chữ nhật lớn nhất dưới biểu đồ trong python

Giả sử chúng ta có một danh sách các số đại diện cho chiều cao của các thanh trong biểu đồ. Chúng ta phải tìm diện tích của hình chữ nhật lớn nhất có thể được tạo thành dưới các thanh.

Vì vậy, nếu đầu vào giống như nums =[3, 2, 5, 7]

thì đầu ra sẽ là 10

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• stk:=một ngăn xếp và ban đầu chèn -1 vào nó
• chèn số 0 vào cuối độ cao
• ans:=0
• đối với tôi trong phạm vi từ 0 đến kích thước chiều cao, hãy thực hiện
  • while heights [i]
  • h:=heights [top of stk] và pop from stk
  • w:=i - top of stk - 1
  • ans:=tối đa ans và (h * w)
• đẩy tôi vào stk

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

[3, 2, 5, 7]

Đầu ra

10