ข้อ 8 · LC334 Increasing Triplet Subsequence 🟡

ขั้นที่ 1 · โจทย์นี้ขออะไรจริง ๆ

คำสำคัญที่สุดของข้อนี้คือ โจทย์ขอแค่ true หรือ false ไม่ได้ขอว่าสามตัวนั้นคือตัวไหน

ความต่างนี้เปลี่ยนความยากของข้อทั้งข้อ เพราะเมื่อไม่ต้องรายงานว่าใครคือใคร เราจึงไม่ต้องเก็บตำแหน่งหรือชุดคำตอบไว้เลย

อีกคำที่ต้องอ่านให้แตกคือ ไม่ต้องอยู่ติดกัน สามตัวอาจอยู่ห่างกันแค่ไหนก็ได้ ขอแค่ลำดับตำแหน่งและลำดับค่าถูกต้อง

ขั้นที่ 2 · กับดักแรก — เช็คแค่สามตัวที่ติดกัน

วิธีที่คิดออกเร็วที่สุดคือไล่ดูสามตัวติดกันทีละชุด ซึ่งเขียนง่ายและเร็ว แต่ผิด

def wrong(nums):
    for i in range(len(nums)-2):
        if nums[i] < nums[i+1] < nums[i+2]:
            return True
    return False

def right(nums):
    first = second = float("inf")
    for x in nums:
        if x <= first: first = x
        elif x <= second: second = x
        else: return True
    return False

for nums in [[1,2,3,4,5], [5,4,3,2,1], [2,1,5,0,4,6], [20,100,10,12,5,13]]:
    w, r = wrong(nums), right(nums)
    mark = "" if w == r else "   <- ต่างกัน!"
    print(f"nums={nums} | เช็คติดกัน -> {w} | วิธีถูก -> {r}{mark}")

print()
print("nums=[20,100,10,12,5,13] มีคำตอบคือ 10 < 12 < 13 (ตำแหน่ง 2,3,5) ซึ่งไม่ติดกัน")

nums=[1, 2, 3, 4, 5] | เช็คติดกัน -> True | วิธีถูก -> True
nums=[5, 4, 3, 2, 1] | เช็คติดกัน -> False | วิธีถูก -> False
nums=[2, 1, 5, 0, 4, 6] | เช็คติดกัน -> True | วิธีถูก -> True
nums=[20, 100, 10, 12, 5, 13] | เช็คติดกัน -> False | วิธีถูก -> True   <- ต่างกัน!

nums=[20,100,10,12,5,13] มีคำตอบคือ 10 < 12 < 13 (ตำแหน่ง 2,3,5) ซึ่งไม่ติดกัน

สามเคสแรกให้ผลตรงกัน มีแค่เคสสุดท้ายที่ต่าง ซึ่งเป็นเหตุผลที่หลายคนส่งคำตอบผิดไปโดยมั่นใจ

ขั้นที่ 3 · กุญแจของข้อนี้

กุญแจคือถามว่า ถ้าจะรู้ว่ามีสามตัวเรียงเพิ่มขึ้น เราต้องจำอะไรไว้น้อยที่สุด

คำตอบคือจำแค่สองค่า ให้นึกภาพว่าเราเดินไปเรื่อย ๆ ในมือถือกระดาษสองแผ่น แผ่นแรกจดค่าที่เล็กที่สุดที่เคยเจอ แผ่นที่สองจดค่าที่เล็กเป็นอันดับสองที่มาหลังแผ่นแรก

พอเจอตัวที่ใหญ่กว่าทั้งสองแผ่น ก็แปลว่ามีสามตัวเรียงเพิ่มขึ้นครบแล้ว ตอบ true ได้ทันที

ทำไมต้องพยายามให้สองค่านี้เล็กที่สุดเท่าที่จะเป็นได้ เพราะยิ่งเล็กยิ่งเปิดโอกาสให้ตัวข้างหน้าใหญ่กว่ามันได้ง่ายขึ้น

ขั้นที่ 4 · เดินตามโค้ดทีละสเต็ป

def triplet(nums):
    first = second = float("inf")
    for i, x in enumerate(nums):
        if x <= first:
            first = x
            print(f"  i={i} x={x}: เล็กกว่าหรือเท่า first -> first={first} second={second}")
        elif x <= second:
            second = x
            print(f"  i={i} x={x}: อยู่ระหว่าง -> first={first} second={second}")
        else:
            print(f"  i={i} x={x}: ใหญ่กว่าทั้งคู่ -> เจอครบสามตัวแล้ว!")
            return True
    return False

print("nums=[2,1,5,0,4,6] ->", triplet([2,1,5,0,4,6]))

  i=0 x=2: เล็กกว่าหรือเท่า first -> first=2 second=inf
  i=1 x=1: เล็กกว่าหรือเท่า first -> first=1 second=inf
  i=2 x=5: อยู่ระหว่าง -> first=1 second=5
  i=3 x=0: เล็กกว่าหรือเท่า first -> first=0 second=5
  i=4 x=4: อยู่ระหว่าง -> first=0 second=4
  i=5 x=6: ใหญ่กว่าทั้งคู่ -> เจอครบสามตัวแล้ว!
nums=[2,1,5,0,4,6] -> True

ขั้นที่ 5 · จุดที่ทุกคนสะดุด และเป็นหัวใจของข้อนี้

ดูบรรทัด i=3 ให้ดี ค่า first ถูกเปลี่ยนจาก 1 เป็น 0 ทั้งที่ second เป็น 5 ซึ่งถูกตั้งไว้ตอน first ยังเป็น 1

ถ้าอ่านตามตัวอักษร ตอนนี้ first คือเลข 0 ที่ตำแหน่ง 3 ส่วน second คือเลข 5 ที่ตำแหน่ง 2 แปลว่า second อยู่ ก่อน first ซึ่งขัดกับกติกาที่เราตั้งไว้

หลายคนถึงตรงนี้จะสรุปว่าโค้ดผิด แต่คำตอบสุดท้ายยังถูกต้องเสมอ และเหตุผลอยู่ที่ตัวคำถามของโจทย์

เพราะโจทย์ถามแค่ว่า มีสามตัวเรียงเพิ่มขึ้นอยู่จริงไหม ไม่ได้ถามว่าสามตัวนั้นคือตัวไหน โค้ดจึงไม่จำเป็นต้องรักษาให้ first กับ second เป็นคู่ที่ถูกต้องตลอดเวลา

ที่ตำแหน่ง 5 มีคำตอบให้เลือกถึงสองชุด คือ (1, 5, 6) จากตำแหน่ง 1, 2, 5 และ (0, 4, 6) จากตำแหน่ง 3, 4, 5 ทั้งสองชุดถูกต้องพร้อมกัน

ขั้นที่ 6 · ทำไมต้องใช้ <= ไม่ใช่ <

โจทย์ต้องการค่าที่เพิ่มขึ้นจริง ไม่ใช่เท่ากัน ดังนั้นค่าซ้ำต้องไม่นับเป็นการเพิ่ม

การเขียน x <= first ทำให้ค่าที่เท่ากับ first ไปอัปเดต first แทนที่จะเลื่อนไปเป็น second ซึ่งกัน [2, 2, 2] ไม่ให้ตอบ true ผิด ๆ

ถ้าเผลอใช้ < ทั้งสองที่ ลิสต์ที่มีค่าซ้ำกันอาจให้คำตอบผิดได้