LeetCode 11 Container With Most Water: ทำไมต้องขยับฝั่งเตี้ย

โจทย์ให้ความสูงของเส้นแนวตั้งตามตำแหน่ง แล้วเลือกสองเส้นเพื่อกักน้ำให้พื้นที่มากที่สุดครับ พื้นที่คือระยะห่างคูณความสูงของฝั่งที่เตี้ยกว่า เพราะน้ำล้นตรงขอบนั้น

WHY: two pointers ชนะด้วยการทิ้งสิ่งที่พิสูจน์ว่าไม่ดีขึ้น

brute force ลองทุกคู่ O(n²) และใช้ O(1) memory วิธี suffix maximum เก็บ candidate ทางขวาที่สูงขึ้นเรื่อย ๆ ช่วยตัดบางคู่แต่ยังซับซ้อนและ worst case อาจใกล้ O(n²) พร้อม O(n) memory

two pointers เริ่มที่ปลายทั้งสอง พื้นที่มี width ใหญ่สุด จากนั้นขยับฝั่งเตี้ยเข้าด้านใน หากขยับฝั่งสูงแต่คงฝั่งเตี้ยเดิม width ลดลงและความสูงจำกัดยังไม่เพิ่ม จึงไม่มีทางได้พื้นที่ดีกว่า คู่ที่ใช้ฝั่งเตี้ยนั้นถูกตัดได้ทั้งหมด

HOW: ใช้ brute force เป็น oracle ของวิธีเร็ว

import unittest


def max_area_brute(heights):
    return max((j - i) * min(heights[i], heights[j])
               for i in range(len(heights))
               for j in range(i + 1, len(heights)))


def max_area_two_pointers(heights):
    left, right, best = 0, len(heights) - 1, 0
    while left < right:
        best = max(best, (right - left) * min(heights[left], heights[right]))
        if heights[left] <= heights[right]:
            left += 1
        else:
            right -= 1
    return best


def max_area_candidates(heights):
    candidates = []
    tallest = -1
    for index in range(len(heights) - 1, -1, -1):
        if heights[index] > tallest:
            candidates.append(index)
            tallest = heights[index]
    best = 0
    for left in range(len(heights)):
        for right in candidates:
            if right > left:
                best = max(best, (right - left) * min(heights[left], heights[right]))
    return best


class AreaTests(unittest.TestCase):
    def test_methods(self):
        cases = [([1, 1], 1), ([1, 8, 6, 2, 5, 4, 8, 3, 7], 49), ([4, 3, 2, 1, 4], 16)]
        for function in (max_area_brute, max_area_two_pointers, max_area_candidates):
            for heights, expected in cases:
                self.assertEqual(function(heights), expected)


if __name__ == "__main__":
    unittest.main()

ตารางตัดสินใจ

เงื่อนไข	วิธี	เวลา	memory	เหตุผล
production/default	two pointers	O(n)	O(1)	เร็วและพิสูจน์การตัดได้
input เล็ก/ทำ oracle	brute force	O(n²)	O(1)	ตรวจ implementation อื่นง่าย
ทดลอง pruning	suffix candidates	worst O(n²)	O(n)	ไม่คุ้มกว่า default

best default คือ two pointers เมื่อเข้าถึง array ได้ทั้งสองปลาย วิธีนี้ไม่เหมาะกับ streaming ที่เห็นข้อมูลครั้งเดียว เพราะคำตอบต้องจับคู่กับอนาคตและไม่มี bound เล็กที่เก็บพอเสมอ หากข้อมูลใหญ่อยู่ภายนอก memory ต้องใช้ random access storage หรือเปลี่ยนโจทย์

edge cases ตามโจทย์ควรมีอย่างน้อยสองเส้น ความสูงศูนย์ได้ และค่ามากต้องระวัง overflow ในภาษาที่ integer จำกัด Python ไม่มีปัญหานี้ แต่ Java ควรพิจารณา long

Recap

• พื้นที่ถูกจำกัดโดยฝั่งเตี้ย
• เมื่อ width ลด ต้องทิ้งฝั่งเตี้ยเพื่อมีโอกาสเพิ่มขอบจำกัด
• two pointers ให้ O(n) time และ O(1) memory
• เก็บ brute force เป็น test oracle สำหรับ input เล็ก
• streaming แบบครั้งเดียวไม่เข้ากับวิธี exact นี้โดยธรรมชาติ

ฝึกเขียน invariant ว่าอะไรถูกตัดในแต่ละก้าว จะจำอัลกอริทึมได้นานกว่าจำโค้ดครับ