ข้อ 12 · LC11 Container With Most Water 🟡

โจทย์นี้มีอะไรแอบซ่อนอยู่ พออ่านครั้งแรกเหมือนเรขาคณิต แต่พอเห็นมุมมองที่ถูก มันกลายเป็น two pointers ที่เดินรอบเดียวจบ

ของยากไม่ใช่โค้ด — โค้ดสั้นมาก ของยากคือสร้าง intuition ว่าทำไมวิธีนี้ถึงถูก นั่นคือสิ่งที่หน้านี้โฟกัส เริ่มจากศูนย์เลย

โจทย์พูดว่าอะไร

ให้ integer array height ความยาว n มีเส้นแนวตั้ง n เส้น จุดปลายของเส้นที่ i อยู่ที่ (i, 0) และ (i, height[i])

หาเส้นสองเส้นที่รวมกับแกน x แล้วได้ภาชนะจุน้ำได้มากที่สุด แล้ว return ปริมาณน้ำนั้น — ห้ามเอียงภาชนะ

Understanding the Area Formula

ก่อนกระโดดไปเฉลย ต้องชัดก่อนว่าคำนวณพื้นที่ยังไง

ถ้าเลือกเส้นที่ตำแหน่ง i กับ j (โดย i < j) น้ำที่กักได้คือ

Area = width × height
     = (j − i) × min(height[i], height[j])

ความสูงใช้ min() เพราะน้ำล้นออกทางเส้นที่เตี้ยกว่า
— เติมสูงกว่าเส้นเตี้ยไม่ได้

Step 1 — Brute Force

เริ่มจากวิธีตรง ๆ ตามปกติ เช็คทุกคู่เส้นที่เป็นไปได้ แล้วเก็บค่ามากสุด

def max_area(height: list[int]) -> int:
    max_water = 0
    n = len(height)

    for i in range(n):
        for j in range(i + 1, n):
            width = j - i
            h = min(height[i], height[j])
            area = width * h
            max_water = max(max_water, area)

    return max_water


print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))

49

Step 2 — Building the Intuition

นี่คือส่วนสำคัญที่สุดของทั้งหน้า อ่านช้า ๆ

เริ่มด้วยตัวชี้สองตัว — ตัวหนึ่งที่เส้นซ้ายสุด (index 0) อีกตัวที่เส้นขวาสุด (index n−1) นี่คือความกว้างมากที่สุดที่เป็นไปได้

คำนวณพื้นที่แล้ว ถามต่อ: ควรขยับ left หรือ right?

The Proof — ทำไมต้องขยับฝั่งเตี้ยเสมอ

สมมติเส้นซ้ายสูง 3 เส้นขวาสูง 8 พื้นที่ตอนนี้ถูกจำกัดที่ 3 (ฝั่งที่เตี้ยกว่า)

นี่คือทั้งอัลกอริทึม ของอื่น ๆ — โค้ด ลูป — เป็นแค่การลงมือทำ insight เดียวนี้

พิสูจน์แบบตัดคู่ทิ้ง (แบบที่ interviewer ชอบถาม)

สมมติ height[left] < height[right] เราจะขยับ left เข้ามา แปลว่าทิ้งคู่ทั้งหมดที่ยังใช้เส้น left ตัวนี้เป็นผนังกับเส้นอื่นที่แคบกว่า right

คู่ปัจจุบัน: area = height[left] × (right − left)

พิจารณาคู่ (left, j) ใด ๆ ที่ left < j < right:
  area' = min(height[left], height[j]) × (j − left)

กรณีที่ 1 — height[j] ≥ height[left]:
  area' = height[left] × (j − left)
        < height[left] × (right − left)   เพราะ j < right
  → น้อยกว่าคู่ปัจจุบัน

กรณีที่ 2 — height[j] < height[left]:
  area' = height[j] × (j − left)
        < height[left] × (right − left)   เพราะทั้งสูงและกว้างน้อยกว่า
  → น้อยกว่าคู่ปัจจุบัน

สรุป: ไม่มีคู่ไหนที่ใช้ left เป็นผนังแล้วจับกับ j ที่แคบกว่า
จะใหญ่กว่าคู่ปัจจุบันได้ → ทิ้ง left ได้ปลอดภัย

กรณี height[right] เตี้ยกว่า ก็สมมาตรกัน — ทิ้งฝั่งขวาได้ด้วยเหตุผลเดียวกัน

Step 3 — Full Dry Run

ไล่ Example 1 ให้จบทั้งก้อน

height  = [1, 8, 6, 2, 5, 4, 8, 3, 7]
index   = [0, 1, 2, 3, 4, 5, 6, 7, 8]
maxArea = 0

สังเกต Step 4: สองฝั่งสูงเท่ากัน (ทั้งคู่เป็น 8) ขยับข้างไหนก็ได้ เพราะความสูงยังติดเพดานที่ 8 อยู่ดี แถมความกว้างลด — พื้นที่ไม่มีทางโตขึ้นจากคู่นี้

Step 4 — The Optimal Solution

หลังสร้าง intuition แล้ว โค้ดสั้นและสะอาดมาก

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0                     # เริ่มที่เส้นซ้ายสุด
        right = len(height) - 1      # เริ่มที่เส้นขวาสุด
        max_water = 0                # พื้นที่มากสุดที่เคยเจอ

        while left < right:
            # พื้นที่ = กว้าง x สูง โดยสูงถูกจำกัดด้วยเส้นที่เตี้ยกว่า
            width = right - left
            h = min(height[left], height[right])
            max_water = max(max_water, width * h)

            # ขยับตัวชี้ที่ชี้เส้น "เตี้ยกว่า" เข้ามา
            # เพราะขยับฝั่งสูงมีแต่ทำให้แคบลงโดยความสูงไม่เพิ่ม
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_water

Step 5 — Complexity Analysis

Why It’s O(n) — ไล่เหตุผลทีละข้อ

• left เริ่มที่ 0 แล้วเพิ่มอย่างเดียว
• right เริ่มที่ n−1 แล้วลดอย่างเดียว
• แต่ละรอบขยับพอดีหนึ่งตัว หนึ่งช่อง
• ลูปหยุดเมื่อ left >= right
• จำนวนรอบรวม ≤ n−1 (สองตัวไม่มีทางไขว้กัน)
• งานในรอบเป็น O(1) — ลบครั้งหนึ่ง, min ครั้งหนึ่ง, คูณครั้งหนึ่ง, เทียบครั้งหนึ่ง
• รวม: O(n) time

Step 6 — Common Wrong Approaches

Wrong 1 — ขยับทั้งสองฝั่งพร้อมกันทุกก้าว

บางคนคิดว่า “บีบเข้ามาทีละข้างพร้อมกัน” — ผิด เพราะจะข้ามคู่ที่ถูกต้อง คำตอบอาจต้องขยับแค่ซ้ายหลายก้าวติดกัน

Wrong 2 — ขยับฝั่งสูง

พลาดที่เจอบ่อยที่สุด บางคนคิดว่า “เส้นสูงมีส่วนกับความสูงมากกว่า เลยควรเก็บไว้…” หรือสับสนไปมาว่าขยับฝั่งไหน

กลับไปอ่านพิสูจน์ใน Step 2: ขยับฝั่งสูง → กว้างลด ความสูงยังติดเพดานเส้นเตี้ยเดิม → พื้นที่ไม่มีทางโต

Wrong 3 — เริ่มจากเส้นสูงสุดแล้วขยายออก

บางคนหาเส้นสูงสุดก่อนแล้วค่อยหาคู่ — ไม่เวิร์ก เพราะบ่อที่ดีที่สุดไม่จำเป็นต้องใช้เส้นที่สูงที่สุดเลย พื้นที่ขึ้นกับทั้งความสูงและความกว้าง บ่อกว้างที่สูงปานกลางชนะบ่อแคบที่สูงมากได้ (ใน Example 1 เส้นสูง 8 สองเส้นได้แค่ 40 < 49)

Step 7 — Edge Cases

Step 8 — อธิบายในสัมภาษณ์ยังไง

ข้อนี้เป็นของโปรดที่ Amazon, Google, Microsoft นี่คือลำดับที่ควรพูด

1. Restate: “หาสองเส้นที่ maximize กว้าง × ความสูงที่เตี้ยกว่า”
2. Brute force: “ลองทุกคู่ O(n²) ได้ แต่ช้าไป ต้องการ O(n)”
3. Intuition: “พื้นที่ถูกจำกัดด้วยเส้นเตี้ย ถ้าขยับฝั่งสูง ความกว้างลดและความสูงไม่มีทางดีขึ้น → พื้นที่ไม่มีทางโต ดังนั้นต้องขยับฝั่งเตี้ยเสมอ”
4. Algorithm: “เริ่มปลายทั้งสองข้างเพื่อได้กว้างสุด ขยับฝั่งเตี้ยเข้ามาทีละก้าว เก็บพื้นที่มากสุดตลอดทาง”
5. Code: เขียน ~15 บรรทัด
6. Complexity: “O(n) time, O(1) space — แต่ละตัวชี้ขยับได้ไม่เกิน n ครั้ง”
7. Edge cases: ยาว 2, สูงเท่ากันหมด, คำตอบอยู่ก้าวแรก

ข้อนี้ต่างจาก Two Sum II ยังไง

Final Solution at a Glance

def max_area(height: list[int]) -> int:
            left, right, max_water = 0, len(height) - 1, 0

            while left < right:
                area = (right - left) * min(height[left], height[right])
                max_water = max(max_water, area)

                if height[left] < height[right]:
                    left += 1
                else:
                    right -= 1

            return max_water

Wrapping Up — จำสามอย่างนี้พอ

ข้อนี้เป็นโจทย์ที่ “อ๋อ” ดังมาก พอเข้าใจว่าพื้นที่ถูกจำกัดด้วยเส้นเตี้ย และการขยับฝั่งสูงจึงเป็นการเสียของฟรี — เฉลย two pointers ก็ชัดขึ้นทันที

1. Area = กว้าง × min(height[left], height[right])
2. ขยับตัวชี้ที่ชี้เส้นเตี้ยกว่าเข้ามาเสมอ
3. อย่าหยุดกลางคัน — วิ่งจน left ชน right เพราะค่าสูงสุดอาจอยู่ก้าวไหนก็ได้

สามข้อนี้บวกพิสูจน์ว่าทำไมมันเวิร์ก คือสิ่งที่ต้องพกเข้าห้องสัมภาษณ์