Container With Most Water ใน Python - หาพื้นที่น้ำมากที่สุด

สมมติว่าเรามีชุดจำนวนเต็มไม่ติดลบ n ตัว a1, a2, ..., an แต่ละค่าแทนจุดที่พิกัด (i, a[i]) มีเส้นตั้ง n เส้น ที่ปลายสองข้างของเส้น i อยู่ที่ (i, a[i]) และ (i, 0) เราต้องหาสองเส้นที่ร่วมกับแกน x สร้างภาชนะ (container) ให้ปริมาตรน้ำมากที่สุด ตัวอย่าง [1,8,6,2,5,4,8,3,7] ผลลัพธ์ 49

ในส่วนที่ทับสี สูง 7 และกว้าง 7 ช่วง พื้นที่รวม = 7 * 7 = 49

ขั้นตอนการทำงาน (Two Pointers)

1. low := 0, high := len(arr) - 1, ans := 0
2. วนลูป while low < high:
   • ถ้า arr[low] < arr[high]: min_h := height[low], min_ind := low
   • มิฉะนั้น: min_h := height[high], min_ind := high
   • ans := max((high - low) * min_h, ans)
   • ถ้า low + 1 == min_ind + 1: low += 1 มิฉะนั้น high -= 1
3. คืนค่า ans

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

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

อินพุต

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

เอาต์พุต

49