ข้อ 16 · LC1004 Max Consecutive Ones III (หนึ่งต่อเนื่องมากสุด พลิก k) 🟡

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

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

ใช้ Sliding Window ขนาดยืดหยุ่น (variable size) กุญแจคือเปลี่ยนมุมมอง: "พลิก 0 ได้ k ตัว" เท่ากับ "window ที่ยาวที่สุดที่มี 0 ไม่เกิน k ตัว" เพราะ 0 ทุกตัวใน window พลิกเป็น 1 ได้ตราบใดที่ไม่เกิน k

brute force ลองทุกช่วงแล้วนับ 0 เป็น O(n²) ช้า Sliding Window ขยายขวารับของเข้าเรื่อย ๆ track จำนวน 0 ไว้ ถ้าเกิน k ค่อยหดซ้าย จึงเหลือ O(n)

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

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

ลองไล่ nums = [1, 1, 0, 0, 1], k = 1 ดูว่า left หดตอนไหน

best = 3 (ช่วง [1, 1, 0] พลิก 0 หนึ่งตัวได้ 1 สามตัว)

def longest_ones(nums, k):
    left = 0
    zeros = 0            # จำนวน 0 ในหน้าต่างตอนนี้
    best = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1                 # รับตัวใหม่ทางขวา
        while zeros > k:               # 0 เกินโควตาพลิก
            if nums[left] == 0:
                zeros -= 1             # หดซ้าย ถอด 0 ออก
            left += 1
        best = max(best, right - left + 1)   # หน้าต่างตอนนี้ถูกต้อง
    return best

print(longest_ones([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2))  # 6

6