ผลรวมหน้าต่างขนาดคงที่

งานจำนวนมากต้องหาผลรวมของทุกช่วงที่มีสมาชิกต่อเนื่องกัน k ตัว การคำนวณผลรวมของแต่ละช่วงใหม่ตั้งแต่ต้นเป็นการทำงานที่สิ้นเปลือง และยังมีวิธีที่ดีกว่านั้นครับ 🪟

แนวคิดแบบตรงไปตรงมาคือบวกสมาชิกในแต่ละหน้าต่างที่มีความยาว k แยกกัน วิธีนี้ทำงานซ้ำและมีต้นทุน O(n คูณ k) ซึ่งช้าเกินไปสำหรับข้อมูลขาเข้าขนาดใหญ่

หน้าต่างที่อยู่ติดกันมีส่วนที่ ซ้อนทับกัน เกือบทั้งหมด เมื่อเลื่อนไปทางขวาหนึ่งขั้น เพียงนำสมาชิกซ้ายสุดออก แล้วเพิ่มสมาชิกใหม่หนึ่งตัวทางขวา

เริ่มจากหาผลรวมของสมาชิก k ตัวแรกเพียงครั้งเดียว ผลรวมนี้จะเป็นค่าตั้งต้นที่คุณปรับปรุงต่อไปเมื่อหน้าต่างเลื่อนไปข้างหน้า

หากต้องการเลื่อนหน้าต่าง ให้ add สมาชิกที่เข้ามา แล้วลบสมาชิกที่ออกไป วิธีนี้ทำให้การทำงานในแต่ละขั้นใช้เวลาคงที่ O(1)

หลังจากเลื่อนแต่ละครั้ง ให้อัปเดตค่าที่ต้องการ เช่น ค่าสูงสุดของผลรวมหน้าต่างที่พบจนถึงตอนนี้ ค่าของหน้าต่างจึงพร้อมใช้งานได้ทันทีเสมอ

คุณเข้าถึงสมาชิกแต่ละตัวเพื่อเพิ่มเข้าไปครั้งหนึ่ง และเข้าถึงอีกครั้งเพื่อนำออก ดังนั้นการสแกนทั้งหมดจึงมีความซับซ้อน O(n) และรองรับข้อจำกัดขนาดใหญ่ได้อย่างสบาย

สมาชิกที่ออกจากหน้าต่างคือ a[i - k] ไม่ใช่ a[i - 1] การใช้ระยะชดเชยให้ถูกต้องเป็นสิ่งที่มักผิดพลาดที่สุดในหน้าต่างความยาวคงที่

ต้องการหาค่า เฉลี่ยสูงสุดของหน้าต่างแทนผลรวมหรือไม่ เพียงหารผลรวมของหน้าต่างที่ติดตามไว้ด้วย k ตรรกะการเลื่อนหน้าต่างไม่ต้องเปลี่ยนแปลงเลย

หากอาร์เรย์มีจำนวนสมาชิก น้อยกว่า k จะไม่มีหน้าต่างที่สมบูรณ์ ตรวจสอบ len(a) เทียบกับ k ตั้งแต่ต้น แล้วคืนค่าทันทีเพื่อหลีกเลี่ยงข้อผิดพลาดจากการใช้ดัชนี

ใช้รูปแบบนี้เมื่อหน้าต่างมี ความยาวคงที่ และคุณรวมค่าต่าง ๆ ได้อย่างประหยัด เช่น ผลรวม จำนวน หรือสถิติสะสมอย่างง่าย

คุณเลื่อนหน้าต่างขนาด k ไปทางขวาทีละขั้นผ่านอาร์เรย์

ตั้งต้นหน้าต่างแรกเพียงครั้งเดียว จากนั้น บวกและลบ ในแต่ละขั้นเพื่อเลื่อนหน้าต่างด้วยเวลา O(1) การสแกนหน้าต่างขนาดคงที่ทั้งหมดจึงใช้เวลาเชิงเส้น ✅