ข้อ 25 · LC735 Asteroid Collision (ดาวเคราะห์น้อยชนกัน) 🟡

ข้อนี้เห็นภาพชัดว่าทำไมต้องใช้ Stack — เก็บผู้รอดไว้ในกระป๋อง แล้วให้ดวงใหม่ไล่ประลองกับตัวบนสุด

1. ปลดล็อกไอเดีย (Mindset Shift)

โจทย์จำลองอวกาศที่มีดาวเคราะห์น้อยเรียงแถวกัน:

• ค่าบวก (+) = ดาวพุ่งไปทาง "ขวา"
• ค่าลบ (−) = ดาวพุ่งไปทาง "ซ้าย"
• ตัวเลข = ขนาดของดาว

หัวใจสำคัญ: ดาวชนกันได้กรณีเดียวเท่านั้น — "ดาวดวงซ้ายพุ่งขวา (+) และดาวดวงขวาพุ่งซ้าย (−)" วิ่งมาประสานงา (เหมือนรถวิ่งสวนเลน) · ชนแล้วดวงเล็กระเบิด · ขนาดเท่ากันระเบิดทั้งคู่

ใช้ Stack เป็นกระป๋องเก็บผู้รอดชีวิต — หยิบดาวดวงใหม่ทีละดวง ถ้าต้องชนกับตัวบนสุด ก็เปิดลานประลองว่าใครอยู่ใครไป

2. กฎเหล็ก 3 ข้อ (The Logic)

สร้าง Stack ว่าง แล้วหยิบดาวมาพิจารณาทีละดวง (a):

1. กฎแห่งความสงบสุข — ดาวใหม่ลงกระป๋องได้ปลอดภัยเมื่อ: กระป๋องว่าง หรือ ดาวใหม่พุ่งขวา (+) หรือ ตัวบนสุดพุ่งซ้าย (−) (วิ่งแยกย้าย)
2. กฎลานประลอง — เปิดเมื่อตัวบนสุดเป็น (+) แต่ตัวใหม่เป็น (−): ตัวบนเล็กกว่า → pop แล้วสู้ต่อ · ขนาดเท่ากัน → pop ทั้งคู่ (alive = False) · ตัวบนใหญ่กว่า → ตัวใหม่ตาย (alive = False)
3. คนจริงเท่านั้นที่อยู่รอด — ถ้าดาวใหม่เคลียร์กระป๋องได้หมด หรือไม่มีใครให้สู้แล้ว ถึงจะมีสิทธิ์ append เข้า Stack

3. โค้ด Python (LeetCode Ready)

แปลงกฎลานประลองเป็นโค้ด โดยใช้ตัวแปร alive บอกว่าดาวดวงใหม่ยังรอดไหม:

class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        stack = []

        for a in asteroids:
            alive = True  # สมมติให้ดาวดวงใหม่รอดไว้ก่อน

            # เปิดลานประลอง: แชมป์เก่าพุ่งขวา (+) เจอ ผู้ท้าชิงพุ่งซ้าย (−)
            while stack and stack[-1] > 0 and a < 0:

                # เช็คขนาด: แชมป์เก่า VS ผู้ท้าชิง (abs ถอดเครื่องหมายก่อนเทียบ)
                if stack[-1] < abs(a):
                    stack.pop()  # แชมป์เก่าตัวเล็กกว่า → ระเบิด!
                    continue     # ผู้ท้าชิงชนะ วนไปสู้คนถัดไป

                elif stack[-1] == abs(a):
                    stack.pop()   # ขนาดเท่ากัน → แชมป์เก่าระเบิด...
                    alive = False # ...และผู้ท้าชิงก็ระเบิดคู่ด้วย

                else:
                    alive = False  # แชมป์เก่าใหญ่กว่า → ผู้ท้าชิงระเบิดตาย

                # ถ้าผู้ท้าชิงตายแล้ว จบการต่อสู้
                break

            # ถ้าผู้ท้าชิงรอด ก็เชิญเข้ากระป๋อง
            if alive:
                stack.append(a)

        return stack

3.5. อธิบายโค้ดฉบับละเอียด — บรรทัดต่อบรรทัด

โค้ดฉบับนี้ใช้หลักการ "เอาดาวดวงใหม่ ไปไล่ชนดาวที่อยู่ใน stack (กล่องเก็บดาว)" ทีละตัวจนกว่าจะรู้ผล ครบทุกบรรทัด:

class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        stack = []

        for a in asteroids:
            alive = True  # สมมติไว้ก่อนว่า ดาวดวงนี้ "รอดชีวิต"

            # เปิดลานประลอง: แชมป์เก่าพุ่งขวา (+) เจอ ผู้ท้าชิงพุ่งซ้าย (−)
            while stack and stack[-1] > 0 and a < 0:

                # เช็คขนาด: แชมป์เก่า VS ผู้ท้าชิง (abs ถอดเครื่องหมายก่อนเทียบ)
                if stack[-1] < abs(a):
                    stack.pop()  # แชมป์เก่าตัวเล็กกว่า → ระเบิด!
                    continue     # ผู้ท้าชิงชนะ วนไปสู้คนถัดไป

                elif stack[-1] == abs(a):
                    stack.pop()   # ขนาดเท่ากัน → แชมป์เก่าระเบิด...
                    alive = False # ...และผู้ท้าชิงก็ระเบิดคู่ด้วย

                else:
                    alive = False  # แชมป์เก่าใหญ่กว่า → ผู้ท้าชิงระเบิดตาย

                # ถ้าผู้ท้าชิงตายแล้ว จบการต่อสู้
                break

            # ถ้าผู้ท้าชิงรอด ก็เชิญเข้ากระป๋อง
            if alive:
                stack.append(a)

        return stack

<b>📦 บล็อก 1 · เตรียมกล่องเก็บดาว</b>

stack = []           # กล่องเก็บดาวเคราะห์ที่รอดชีวิต
# สำหรับ [10, 2, -5]: ยังไม่วนลูปเลย → stack = []

stack = []

บรรทัดนี้สร้าง stack ว่าง — เปรียบเสมือนกระป๋อง Pringles ว่างๆ รอดรับดาวที่รอดชีวิต

<b>📦 บล็อก 2 · ลูปหยิบดาวทีละดวง</b>

for a in asteroids:    # หยิบดาวดวงใหม่ (a) มาทีละดวงจากซ้ายไปขวา
    alive = True       # สมมติไว้ก่อนว่า ดาวดวงนี้ "รอดชีวิต"

# ดาวดวงที่ 1: a = 10, alive = True
# ดาวดวงที่ 2: a = 2, alive = True
# ดาวดวงที่ 3: a = -5, alive = True

ลูปนี้จะหยิบดาวจาก array ทีละดวง (a) แล้วตั้งตัวแปร alive = True ไว้ก่อน — สมมติไว้ก่อนว่าดาวดวงใหม่นี้รอดชีวิต จะมาแก้ทีหลังถ้าโดนชนตาย

<b>📦 บล็อก 3 · เงื่อนไขการเข้าสู่สนามชน (while loop)</b>

while stack and stack[-1] > 0 and a < 0:

# เงื่อนไขครบ 3 ข้อถึงจะเข้าลูปชน:
# 1. stack: ต้องมีดาวเหลืออยู่ในกล่องให้ชน
# 2. stack[-1] > 0: ดาวตัวล่าสุดในกล่องต้องพุ่งไปทางขวา (➡️)
# 3. a < 0: ดาวดวงใหม่ต้องพุ่งไปทางซ้าย (⬅️)
# (ถ้าไม่ครบ 3 ข้อนี้นี้ แปลว่าไม่ชนกัน มันจะข้ามลูปนี้ไปเลย)

ลูปชนนี้จะทำงาน ก็ต่อเมื่อเข้าเงื่อนไขครบ 3 ข้อนั้นเท่านั้น — เปรียบเสมือนประตูสนามชนที่เปิดเฉพาะเมื่อดาวสองดวงพุ่งสวนทางกัน (➡️ชน⬅️) เท่านั้น

<b>📦 บล็อก 4 · ข้างในลูป: แบ่งเป็่น 3 เคสการชน</b>

if stack[-1] < abs(a):
    stack.pop()  # แชมป์เก่าตัวเล็กกว่า → ระเบิด!
    continue     # ผู้ท้าชิงชนะ วนไปสู้คนถัดไป

# เคสที่ 1: ดาวดวงใหม่ใหญ่กว่า
# stack.pop() → เตะดาวตัวล่าสุดในกล่องทิ้ง (เพราะมันระเบิด)
# continue → สั่งให้วนลูป while ซ้ำ เพื่อดึงดาวใหม่ไปชนกับดาวตัวถัดไปในกล่องต่อ

เคสนี้ดาวดวงใหม่ใหญ่กว่า — ดาวในกล่องแตกกระจาย แล้ว continue ให้วนไปชนดาวตัวถัดไปในกล่องทันที (ยังไม่จบ!) เปรียบเสมือนดาวดวงใหม่ไล่ทำลายดาวในกล่องทีละดวง

elif stack[-1] == abs(a):
    stack.pop()   # ขนาดเท่ากัน → แชมป์เก่าระเบิด...
    alive = False # ...และผู้ท้าชิงก็ระเบิดคู่ด้วย

# เคสที่ 2: ขนาดเท่ากันเป๊ะ
# stack.pop() → เตะดาวในกล่องทิ้ง (ระเบิด)
# alive = False → ดาวดวงใหม่ก็ตายด้วย (ระเบิดคู่)
# break → จบการชนทันที ข้ามไปดูดาวดวงถัดไปในระบบ

เคสนี้ดาวทั้งคู่ระเบิดพร้อมกัน — ทั้งดาวในกล่องและดาวดวงใหม่ตายหมด (alive = False) แล้ว break ออกจากลูปชน

else:
    alive = False  # แชมป์เก่าใหญ่กว่า → ผู้ท้าชิงระเบิดตาย

# เคสที่ 3: ดาวในกล่องใหญ่กว่า
# alive = False → ดาวดวงใหม่สู้ไม่ได้ ระเบิดตายทันที
# break → จบการชนทันที (เพราะดาวใหม่ตายแล้ว ชนต่อไม่ได้)

เคสนี้ดาวในกล่องใหญ่กว่า — ดาวดวงใหม่ต่อสู้ไม่ได้ ระเบิดตายทันที แล้ว break ออกจากลูป

                break

# ถ้าผู้ท้าชิงรอด ก็เชิญเข้ากระป๋อง
if alive:
    stack.append(a)

# break → จบการชน (อยู่ภายใต้ while loop)
# ถ้า alive ยังเป็น True → ดาวดวงใหม่ผ่านศึกมา alive → เก็บเข้ากล่อง
# ถ้า alive เป็น False → ดาวดวงใหม่ตาย → ไม่เก็บ

break อยู่ภายใต้ if/elif/else — จะจบลูปชนก็ต่อเมื่อเคสที่ 2 หรือ 3 เกิดขึ้น (มีผู้ตาย) ส่วนเคสที่ 1 จะใช้ continue แทน break เพื่อวนชนต่อ

<b>📦 บล็อก 5 · สรุปผลหลังจบการชน</b>

if alive:
    stack.append(a)  # ถ้าดาวดวงใหม่ผ่านศึกมาได้ ยังไม่ตาย ให้เก็บเข้ากล่อง

# alive = True → เก็บดาวเข้า stack
# alive = False → ทิ้งดาวดวงนี้ไป

ถ้าดาวดวงใหม่รอดจากการชนทั้งหมด (alive ยังเป็น True) จึงเก็บเข้า stack — เปรียบเสมือนผู้รอดชีวิตที่ได้เข้าค่าย

<b>🎬 มาดดูเหตุนการณณ์จริงจำลองตามโค้ดนนี่ก้าน!</b>

สมมติโจทย์คือ [10, 2, -5]

# ===== ดาวดวงที่ 1 (a = 10) =====
# ลูป while ไม่ทำงาน เพราะ a ไม่น้อยกว่า 0 (10 > 0)
# alive ยังคงเป็น True → เก็บเข้ากล่อง → stack = [10]

# ===== ดาวดวงที่ 2 (a = 2) =====
# ลูป while ไม่ทำงาน เพราะ a ไม่น้อยกว่า 0 (2 > 0)
# alive ยังคงเป็น True → เก็บเข้ากล่อง → stack = [10, 2]

# ===== ดาวดวงที่ 3 (a = -5) =====
# เริ่มเข้า while loop เพราะ:
#   ✅ stack มีของ → [10, 2]
#   ✅ stack[-1] = 2 (> 0) พุ่งขวา ➡️
#   ✅ a = -5 (< 0) พุ่งซ้าย ⬅️

# รอบที่ 1 ใน while:
#   เช็ค if stack[-1] < abs(a) → 2 < 5 (ใช่! เคสที่ 1 ดาวใหม่ใหญ่กว่า)
#     โค้ดทำ stack.pop() → เตะ 2 ออก เหลือ stack = [10]
#     เจอ continue → วนลูป while อีกครั้งทันที!

# รอบที่ 2 ใน while: (ในกล่องเหลือ 10 พุ่งขวา, ดาวใหม่ -5 ยังรอดมาชนต่อ)
#   เช็คเงื่อนไข → เข้าเคส else (ดาวในกล่อง 10 ใหญ่กว่า ดาวใหม่ 5)
#     โค้ดทำ alive = False → ดาวใหม่ตายแล้ว!
#     เจอ break → หลุดออกจากลูป while ทันที

# หลังจบลูป: if alive: (เป็น False) → ไม่เก็บ -5 เข้ากล่อง

# 🎉 ผลลัพธ์สุดท้ายในกล่องเหลือแค่ [10]

stack = []
stack = [10]
stack = [10, 2]
# a = -5 เข้า while loop
# รอบ 1: 2 < 5 → pop() → stack = [10], continue
# รอบ 2: 10 > 5 → alive = False, break
# if alive → False → ไม่ append
# ✅ ผลลัพธ์: [10]

การไล่โค้ดบรรทัดต่อบรรทัดคู่กับตัวอย่างแบบนี้ ช่วยให้เคลียร์และเข้าใจการทำงานของเวอร์ชันนี้ 100% แล้วหรือยังครับ? ถ้าเข้าใจแล้ว เราพร้อมเอาลอจิกนี้ไปประยุกต์กับโจทย์อื่นต่อกันได้เลยนะครับ!

4. จำลองการทำงาน — asteroids = [10, 2, -5]

คำตอบสุดท้ายที่เหลือรอดคือ [10]

5. จุดระวังตกหลุมพราง (Edge Cases)

เคส "วิ่งหนีกัน (แยกย้าย)" — [-5, 5]:

• ตัวแรก −5 (พุ่งซ้าย) เข้าไปก่อน → stack = [−5]
• ตัวที่สอง 5 (พุ่งขวา) วิ่งแยกย้ายคนละทาง — ไม่ชน!
• เงื่อนไข while stack[-1] > 0 กันไม่ให้เกิดการชน (ตัวบนเป็น −5) → ตอบ [−5, 5]

เคส "กวาดล้างทั้งบาง" — [1, 2, 3, -4]:

−4 เข้ามาตัวเดียวไล่ชน 3, 2, 1 ระเบิดทิ้งเรียบ → ครองกระป๋องคนเดียว ตอบ [−4]

6. Time & Space Complexity

• Time O(n) — แม้ซ้อน while ใน for แต่ดาวแต่ละดวงถูก append แค่ 1 ครั้งและ pop แค่ 1 ครั้ง รวมเป็นเส้นตรง
• Space O(n) — กรณีดาววิ่งแยกย้ายหรือวิ่งทางเดียวกันหมด ต้องยัดทุกดวงลง Stack