Increasing Triplet Subsequence ใน Python

ตรวจสอบว่ามี subsequence เพิ่มขึ้นยาว 3 อยู่ในอาร์เรย์หรือไม่ (ไม่จำเป็นต้องติดกัน)

ตัวอย่าง

Input: [5,3,8,2,7,9,4]
Output: True  # เพราะมี 3,7,9 หรือ 2,7,9

อัลกอริทึม Greedy (O(n) time, O(1) space)

1. เก็บค่า small และ big เริ่มต้นเป็น infinity
2. วนอ่านแต่ละตัว:
   • ถ้า ≤ small → อัปเดต small
   • ถ้า ≤ big → อัปเดต big
   • มิฉะนั้น → พบ triplet แล้ว คืน True
3. จบลูปไม่พบ → คืน False

โค้ด

class Solution:
    def increasingTriplet(self, nums):
        small = big = float('inf')
        for n in nums:
            if n <= small:
                small = n
            elif n <= big:
                big = n
            else:
                return True
        return False

# ทดสอบ
sol = Solution()
print(sol.increasingTriplet([5,3,8,2,7,9,4]))  # True
print(sol.increasingTriplet([5,4,3,2,1]))      # False

สรุป

วิธีนี้ประหยัดหน่วยความจำและรวดเร็ว เหมาะสำหรับสัมภาษณ์เขียนโค้ด