ค่าสูงสุดในหน้าต่างเลื่อนด้วยดีค
รักษาค่าสุดขั้วของหน้าต่างใน O(n)
ค่าสูงสุดในหน้าต่างเลื่อนด้วยดีค เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ค่าสูงสุดของหน้าต่างเลื่อน
เมื่อกำหนดอาร์เรย์และขนาดหน้าต่าง k คุณต้องการหา ค่าสูงสุด ของทุกหน้าต่างขณะเลื่อนไปทางขวา การทำแบบตรงไปตรงมาใช้เวลา O(n คูณ k)
คำมั่นสัญญาที่รวดเร็วกว่า
ด้วย ดีคิวแบบโมโนโทน คุณสามารถหาคำตอบของทุกหน้าต่างได้ในเวลา O(n) รวม โดยไล่ตรวจอาร์เรย์เพียงรอบเดียว
เก็บดัชนีอีกครั้ง
เก็บ ดัชนี ไว้ในดีคิว ไม่ใช่ค่า ดัชนีช่วยให้คุณตรวจได้ว่าสมาชิกด้านหน้าหลุดออกจากหน้าต่างปัจจุบันแล้วหรือยัง
from collections import deque
dq = deque()
res = []รักษาลำดับจากมากไปน้อย
ดีคิวจะรักษาค่าจากด้านหน้าไปด้านหลังให้ เรียงจากมากไปน้อย ดังนั้นดัชนีด้านหน้าจึงชี้ไปยังค่าสูงสุดของหน้าต่างเสมอ
ตัดส่วนท้ายที่เล็กกว่า
ก่อนเพิ่มดัชนี i ให้นำสมาชิกจากด้านหลังออกตราบใดที่ค่าของสมาชิกเหล่านั้น เล็กกว่า เพราะสมาชิกเหล่านั้นไม่มีทางเป็นค่าสูงสุดในอนาคต
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()เพิ่มดัชนีใหม่
หลังจากล้างส่วนท้ายที่อ่อนกว่าแล้ว ให้ใช้ append เพิ่มดัชนีปัจจุบัน ลำดับของดีคิวจะยังถูกต้องสำหรับขั้นตอนถัดไป
dq.append(i)นำด้านหน้าที่หมดอายุออก
หากดัชนีด้านหน้าอยู่นอกหน้าต่าง ให้ใช้ popleft นำออก หน้าต่างขนาด k จะเริ่มที่ดัชนี i ลบ k บวก 1
if dq[0] <= i - k:
dq.popleft()บันทึกค่าสูงสุดแต่ละค่า
เมื่อหน้าต่างแรกมีสมาชิกครบที่ดัชนี k ลบ 1 แล้ว ด้านหน้า ของดีคิวจะเก็บคำตอบของทุกตำแหน่งถัดไป
if i >= k - 1:
res.append(nums[dq[0]])ระวังลำดับการนำออก
นำด้านหน้าที่หมดอายุออกก่อนอ่านคำตอบ มิฉะนั้นคุณอาจรายงานค่าสูงสุดที่ ออกจาก หน้าต่างไปแล้ว
เหตุใดเวลาจึงเป็นเชิงเส้น
แต่ละดัชนีถูกเพิ่มและนำออกไม่เกินหนึ่งครั้ง ดังนั้นงานของดีคิวจึงใช้เวลา O(1) โดยเฉลี่ยสะสม ต่อขั้นตอน และ O(n) โดยรวม
หน้าต่างค่าต่ำสุด ใช้แนวคิดเดียวกัน
สำหรับ ค่าต่ำสุดของหน้าต่างเลื่อน ให้รักษาดีคิวให้เรียงจากน้อยไปมากแทน เพียงสลับการเปรียบเทียบเมื่อตัดส่วนด้านหลัง
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()ตรวจสอบอย่างรวดเร็ว
ในการหาค่าสูงสุดของหน้าต่างเลื่อน ด้านหน้าของดีคิวแบบโมโนโทนเก็บค่าใดไว้
สรุป: ดีคิวเอาชนะปัญหาหน้าต่างเลื่อน
คุณเก็บ ดีคิว ของดัชนีที่เรียงจากมากไปน้อย โดยตัดส่วนท้ายที่เล็ก ทิ้งด้านหน้าที่หมดอายุ และอ่านค่าด้านหน้าเพื่อหาค่าสูงสุดของแต่ละหน้าต่างในเวลา O(n) 🏆
คำถามที่พบบ่อย
บทเรียน “ค่าสูงสุดในหน้าต่างเลื่อนด้วยดีค” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ค่าสูงสุดในหน้าต่างเลื่อนด้วยดีค” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ค่าสูงสุดในหน้าต่างเลื่อนด้วยดีค”
รักษาค่าสุดขั้วของหน้าต่างใน O(n) คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “ค่าสูงสุดในหน้าต่างเลื่อนด้วยดีค” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- สแตกสำหรับจับคู่วงเล็บ
- สแตกโมโนโทน: สมาชิกที่มากกว่าถัดไป
- คิวและ collections.deque
- ค่าสูงสุดในหน้าต่างเลื่อนด้วยดีค