Container With Most Water (Chứa nhiều nước nhất) trong Python

Giả sử chúng ta có một tập hợp n số nguyên không âm a1, a2, ..., an, mỗi giá trị đại diện cho một điểm tại tọa độ (i, a[i]). Có n đường thẳng đứng sao cho hai đầu mút của đường i là tại (i, a[i]) và (i, 0). Chúng ta phải tìm hai đường, cùng với trục x tạo thành một chứa nước, mục tiêu là tìm hai cột nơi thể tích nước lớn nhất. Ví dụ, nếu mảng là [1,8,6,2,5,4,8,3,7], hình minh họa:

Trong phần tô bóng, chiều cao là 7 và có 7 đoạn, nên diện tích thực tế là 7 * 7 = 49. Đây là đầu ra.

Để giải quyết, chúng ta làm theo các bước sau:

• low := 0, high := độ dài mảng - 1, ans := 0.
• Khi low < high:
  • Nếu arr[low] < arr[high]: min_h := height[low] và min_ind := low.
  • Ngược lại min_h := height[high] và min_ind := high.
  • ans := max((high - low) * min_h, ans).
  • Nếu low + 1 == min_ind + 1, tăng low lên 1, ngược lại giảm high đi 1.
• Trả về ans.

Ví dụ

Xem triển khai sau để hiểu rõ hơn:

class Solution(object):
    def maxArea(self, height):
        low = 0
        high = len(height) - 1
        ans = 0
        while low < high:
            if height[low] < height[high]:
                min_height = height[low]
                min_height_index = low
            else:
                min_height = height[high]
                min_height_index = high
            ans = max(((high - low)) * min_height, ans)
            if low + 1 == min_height_index + 1:
                low += 1
            else:
                high -= 1
        return ans

ob1 = Solution()
print(ob1.maxArea([1,8,6,2,5,4,8,3,7]))

Đầu vào

[1,8,6,2,5,4,8,3,7]

Đầu ra

49