เทคนิค sliding-window คืออะไร?

Question

Accepted Answer

เทคนิค **sliding-window** จะรักษาช่วงที่ต่อเนื่องกัน (ช่อง) บนอาร์เรย์หรือสตริง และเลื่อนแทนที่จะคำนวณใหม่ตั้งแต่ต้น เพื่อแก้ปัญหา subarray/substring จำนวนมากใน **O(n)**

## ไอเดีย

ขยายช่องด้วยการเลื่อนขอบด้านขวา ลดลงด้วยการเลื่อนขอบด้านซ้ายเมื่อมีการละเมิดข้อจำกัด นำการคำนวณก่อนหน้านี้มาใช้ใหม่แทนที่จะสแกนซ้ำ

## ตัวอย่าง: ผลรวมสูงสุดของช่องใดก็ได้ขนาด k

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # sum of first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # add new, drop old
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## ความซับซ้อน

- **เวลา:** O(n) — แต่ละองค์ประกอบเข้าและออกจากช่องเพียงครั้งเดียว
- **พื้นที่:** O(1) สำหรับช่องคงที่ O(k) เมื่อติดตามเนื้อหา

## เมื่อใช้ / ข้อมูลเสริม

ใช้สำหรับปัญหา "subarray ยาวที่สุด/สั้นที่สุด/ใหญ่ที่สุด ด้วยคุณสมบัติ X" สำหรับช่อง **ตัวแปร** ให้เลื่อนตัวชี้ด้านซ้ายเพื่อคืนค่าข้อจำกัด ระวังข้อผิดพลาด off-by-one เมื่อเพิ่ม/ลบองค์ประกอบขอบเขต

## ทำไมถึงสำคัญ

Sliding window จะกำจัดงานที่ซ้ำซ้อน โดยเปลี่ยน O(n·k) การคำนวณใหม่เป็นหนึ่งการส่วน

นี่คือรูปแบบปกติสำหรับปัญหา substring และ subarray ที่ปรากฏอย่างต่อเนื่องในสัมภาษณ์

ข้อมูลเชิงลึก — นำผลลัพธ์ก่อนหน้าไปใช้ใหม่แทนการคำนวณใหม่ — สรุปเป็นการสตรีมและข้อมูลแบบเรียลไทม์