ข้อ 17 · LC1493 Longest Subarray of 1's After Deleting One Element (ช่วงหนึ่งยาวสุดหลังลบตัว) 🟡

โจทย์ (LC1493): กำหนด binary array (มีแค่ 0 กับ 1) ชื่อ nums ต้องลบสมาชิก (element) ออกจากอาร์เรย์ 1 ตัวเสมอ ให้ return ขนาดของ subarray ที่ไม่ว่างเปล่าและมีแต่ 1 ล้วนที่ยาวที่สุดในอาร์เรย์ที่เหลือ ถ้าไม่มี subarray แบบนั้นให้ return 0

แนวทาง — ต้องใช้อะไร & คิดยังไง

เป็นน้องของ LC1004 โดยตรง: มองว่า "ต้องลบหนึ่งตัว" คือ "อนุญาตให้ window มี 0 ได้หนึ่งตัว (ตัวที่จะถูกลบ)" ก็ได้ Sliding Window ขนาดยืดหยุ่นแบบ k = 1 ทันที

ความต่างสำคัญคือการนับความยาว: โจทย์บังคับลบหนึ่งตัวเสมอ (แม้ไม่มี 0 เลย) คำตอบจึงเป็นความยาว window ลบหนึ่ง เขียน right - left แทน right - left + 1

1. initialize left = 0, zeros = 0, best = 0
2. iterate right ไปทุก index ถ้า nums[right] == 0 ให้ zeros += 1
3. ขณะที่ zeros > 1 ให้หดซ้าย: ถ้า nums[left] == 0 ลด zeros แล้ว left += 1
4. update best = max(best, right - left) — ไม่ +1 เพราะบังคับลบหนึ่งตัว
5. จบ loop return best

ไล่ทีละสเต็ป

ลองไล่ nums = [1, 1, 0, 1] ดูค่า best (right - left)

best = 3 (window ทั้งหมด [1,1,0,1] ลบ 0 ออกเหลือ 1 สามตัว)

def longest_subarray(nums):
    left = 0
    zeros = 0            # จำนวน 0 ในหน้าต่าง (ยอมได้ไม่เกิน 1)
    best = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1
        while zeros > 1:              # ยอม 0 ได้แค่ตัวเดียว
            if nums[left] == 0:
                zeros -= 1
            left += 1
        # ลบ 1 ตัวเสมอ -> ความยาวหน้าต่าง - 1 = (right - left + 1) - 1
        best = max(best, right - left)
    return best

print(longest_subarray([1, 1, 0, 1]))  # 3
print(longest_subarray([1, 1, 1]))     # 2

3
2