LeetCode #239 Sliding Window Maximum: คิวสองหัวชนะการหา max ทุกหน้าต่าง

โจทย์ Sliding Window Maximum #239 ให้ลิสต์ตัวเลขกับขนาดหน้าต่าง k แล้วขอค่ามากสุดของทุกช่วงต่อเนื่องยาว k

ตัวละคร: หมีขี้เกียจ (max ทีละหน้าต่าง), นากคิว (deque เก็บดัชนีลดลง), บารอน กรรมการ

วิธีหมี — O(n·k)

ทุกจุดเริ่มเรียก max บนช่วง เขียนง่าย ไวท์บอร์ดโอเค แต่ช้าเมื่อ n และ k ใหญ่

วิธีนาก — O(n) ด้วย deque

เก็บดัชนีในคิวสองหัวให้ค่าลดลงจากหัวคิว ไล่ขวาทีละช่อง เอาของหมดอายุและของที่เล็กกว่าออก หัวคิวคือคำตอบของหน้าต่างนั้น (collections.deque)

ตารางเลือก

สถานการณ์	เลือก
สัมภาษณ์	อธิบาย deque
n เล็ก	max ตรงๆ ก็ได้
hot path	deque O(n)

Benchmark (เครื่องนี้ 2026-10-14)

n=20,000, k=50

วิธี	เวลา
deque	3.05 ms
naive max	15.48 ms

โค้ด

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    out = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

assert max_sliding_window([1,3,-1,-3,5,3,6,7], 3) == [3,3,5,5,6,7]
print("ok")

บารอนสรุป

บนอินพุตยาว deque ชนะชัด หมีเหมาะสอนก่อน แล้วค่อยย้ายไปคิว

Recap

• ขอ max ทุกหน้าต่างขนาด k
• naive O(n·k) vs deque O(n)
• Benchmark: 3.05 ms vs 15.48 ms ที่ n=20k k=50