Hình chữ nhật lớn nhất trong Biểu đồ bằng Python

Giả sử chúng ta có một mảng số nguyên đại diện cho chiều cao của biểu đồ. Mỗi thanh có chiều rộng đơn vị. Chúng ta phải tìm hình chữ nhật có diện tích lớn nhất như sau -

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

• Tạo ngăn xếp, đặt i:=0, ans:=0

• while i

  • nếu ngăn xếp có 0 phần tử hoặc chiều cao của phần tử trên cùng ngăn xếp <=height [i], thì

    • chèn i vào ngăn xếp, tăng i lên 1

  • mặt khác -

    • x:=phần tử trên cùng của ngăn xếp, xóa khỏi ngăn xếp.

    • height:=heights [x]

    • temp:=height * (i * stack [-1] - 1) khi ngăn xếp không trống, ngược lại temp:=height * i

    • ans:=max của ans và temp

• trong khi ngăn xếp không trống -

  • x:=phần tử trên cùng của ngăn xếp

  • height:=height [x], xóa khỏi ngăn xếp

  • temp:=height * length of height - phần tử trên cùng của ngăn xếp - 1 khi ngăn xếp là notempty, nếu không thì temp:=length of heights

  • ans:=max của ans và temp

• trả lại ans

Ví dụ

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

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

Đầu vào

[2,1,5,7,3,2]

Đầu ra

12