On this page

ข้อ 14 · LC643 Maximum Average Subarray I (ค่าเฉลี่ย subarray มากสุด) 🟢

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

หา subarray ยาว k ที่มีค่าเฉลี่ยมากที่สุด แล้วคืนค่าเฉลี่ยนั้น

โจทย์ (LC643): กำหนด array จำนวนเต็ม nums ที่มี n สมาชิก และเลขจำนวนเต็ม k ให้หา contiguous subarray (ช่วงต่อเนื่อง) ที่ยาวเท่ากับ k ซึ่งมีค่าเฉลี่ยมากที่สุด แล้ว return ค่าเฉลี่ยนั้น (คำตอบที่คลาดเคลื่อนจากเฉลยไม่เกิน 10⁻⁵ ถือว่าถูกต้อง)

Example 1

Input:: nums = [1, 12, -5, -6, 50, 3], k = 4
Output:: 12.75000
Explanation:: ช่วง [12, -5, -6, 50] ผลรวม (12 - 5 - 6 + 50) = 51 หาร 4 = 12.75 — เป็นช่วงยาว 4 ที่ให้ค่าเฉลี่ยมากที่สุด

Example 2

Input:: nums = [5], k = 1
Output:: 5.00000
Explanation:: มี subarray ยาว 1 แบบเดียวคือ [5] ค่าเฉลี่ยจึงเท่ากับตัวมันเอง

Constraints (ข้อจำกัด)

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
n ถึง 10^5 → ต้องกวาดรอบเดียว วิธีคำนวณผลรวมทุกช่วงใหม่ (O(nk)) รันไม่ทัน

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

ใช้ Sliding Window ขนาดคงที่ (fixed size) k เพราะโจทย์บอกความยาว k มาชัดเจน กุญแจคือค่าเฉลี่ยมากสุดเกิดที่ช่วงที่ผลรวมมากสุด (ทุกช่วงยาว k หารด้วยตัวเดียวกัน) จึงเปลี่ยนโจทย์เป็นหาผลรวมมากสุดของช่วงยาว k แทน

brute force คำนวณผลรวมทุกช่วงยาว k ใหม่หมด เป็น O(nk) ช้าเมื่อ k ใหญ่ Sliding Window เหลือ O(n) เพราะแค่บวกตัวที่เพิ่งเข้าและลบตัวที่เพิ่งออก ไม่ต้องบวกใหม่ทั้งก้อน

สร้าง window แรกด้วย window = sum(nums[:k]) แล้ว initialize best = window
iterate i จาก k ไปจนจบ array
บวกตัวใหม่ที่เข้าทางขวา (window += nums[i])
ลบตัวเก่าที่หลุดออกทางซ้าย (window -= nums[i - k])
update best = max(best, window)
จบ loop return best / k เป็นค่าเฉลี่ย

จุดพลาดที่พบบ่อย

สร้าง window แรกด้วย sum(nums[:k]) และ initialize best = window เสมอ ถ้าเริ่ม best = 0 แล้ว array มีแต่ค่าติดลบ คำตอบจะผิด

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

ลองไล่ nums = [1, 12, -5, -6, 50, 3], k = 4 window แรกคือ [1, 12, -5, -6] รวม = 2

i	ตัวเข้า nums[i]	ตัวออก nums[i-k]	window หลังปรับ	best
เริ่ม	-	-	2	2
4	50	1 (index 0)	2 + 50 - 1 = 51	51
5	3	12 (index 1)	51 + 3 - 12 = 42	51

best = 51 คือผลรวมช่วง [12, -5, -6, 50] คืนค่า 51 / 4 = 12.75

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

def find_max_average(nums, k):
    window = sum(nums[:k])         # ผลรวมหน้าต่างแรก [0, k)
    best = window
    for i in range(k, len(nums)):
        window += nums[i]          # ตัวใหม่เข้าทางขวา
        window -= nums[i - k]      # ตัวเก่าหลุดออกทางซ้าย
        best = max(best, window)
    return best / k                # แปลงผลรวมมากสุดเป็นค่าเฉลี่ย

print(find_max_average([1, 12, -5, -6, 50, 3], 4))  # 12.75

Output

12.75

กุญแจคือค่าเฉลี่ยมากสุดเกิดที่ช่วงที่ผลรวมมากสุด เพราะทุกช่วงยาว k เท่ากันหมด จึงเปลี่ยนโจทย์เป็นหาผลรวมมากสุดของช่วงยาว k ซึ่งง่ายกว่า แล้วค่อยหารด้วย k ตอนท้ายทีเดียว

หัวใจของความเร็วคือเลื่อน window แทนบวก k ตัวใหม่ทุกครั้ง (ซึ่งจะกลายเป็น O(nk)) แค่บวกตัวที่เพิ่งเข้าและลบตัวที่เพิ่งออก ต้อง initialize best = window แรกเสมอ ไม่งั้นกรณีค่าติดลบล้วนจะตอบผิด

Time O(n) สร้าง window แรก O(k) แล้วเลื่อนอีก O(n) รวมยังเป็น O(n) · Space O(1) เก็บแค่ผลรวมกับค่าดีสุด

💡 สรุป pattern

window ขนาดคงที่ k: บวกตัวเข้า ลบตัวออก อย่าคำนวณทั้งช่วงใหม่ และถ้าโจทย์ถามค่าเฉลี่ย ให้แปลงเป็นหาผลรวมก่อนแล้วค่อยหารตอนท้าย