สแตกโมโนโทน: สมาชิกที่มากกว่าถัดไป
ตอบคำถามช่วงได้ในการวนผ่านรอบเดียว
สแตกโมโนโทน: สมาชิกที่มากกว่าถัดไป เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
ปัญหาสมาชิกที่มากกว่าถัดไป
สำหรับตัวเลขแต่ละตัว คุณต้องการค่าที่มากกว่าตัวแรกทางด้านขวา การลองทุกกรณีใช้เวลา O(n ยกกำลังสอง) แต่ สแตกแบบโมโนโทน แก้ปัญหานี้ได้ในการไล่ตรวจเพียงรอบเดียว
ความหมายของโมโนโทน
สแตกแบบโมโนโทน จะเก็บค่าไว้ตามลำดับที่เรียงกัน ในที่นี้คือเรียงจากมากไปน้อย ดังนั้นทันทีที่ลำดับนี้กำลังจะผิดไป เราก็ทราบว่าพบคำตอบแล้ว
เก็บดัชนี ไม่ใช่ค่า
ใส่ ดัชนี ลงในสแตกแทนตัวเลขโดยตรง วิธีนี้ทำให้ทราบแน่ชัดว่าต้องเติมคำตอบลงในตำแหน่งใดเมื่อพบสมาชิกที่มากกว่า
stack = []
ans = [-1] * len(nums)ไล่จากซ้ายไปขวา
วนลูปผ่านอาร์เรย์หนึ่งรอบ ในแต่ละดัชนี คุณจะนำสมาชิกที่พบคำตอบแล้วออก หรือใส่ ดัชนี ปัจจุบันไว้รอภายหลัง
for i in range(len(nums)):นำค่าที่เล็กกว่าออก
ตราบใดที่ค่าปัจจุบันมากกว่าค่าที่ดัชนี ด้านบน ชี้อยู่ ดัชนีด้านบนนั้นก็พบสมาชิกที่มากกว่าถัดไปแล้ว
while stack and nums[i] > nums[stack[-1]]:บันทึกคำตอบ
นำดัชนีด้านบนออก แล้วกำหนดคำตอบของดัชนีนั้นเป็นค่าปัจจุบัน แต่ละดัชนีได้รับการจัดการเพียงครั้งเดียว จึงทำให้งานทั้งหมดมีเวลาเป็น เชิงเส้น
j = stack.pop()
ans[j] = nums[i]ใส่แล้วทำต่อ
หลังจากจัดการค่าที่เล็กกว่าทั้งหมดแล้ว ให้ ใส่ ดัชนีปัจจุบันลงในสแตก เพื่อรอสมาชิกที่มากกว่าของมันในอนาคต
stack.append(i)สมาชิกที่เหลือไม่มีคำตอบ
ดัชนีที่ยังอยู่ในสแตกเมื่อจบการไล่ตรวจไม่เคยพบค่าที่มากกว่า จึงคงค่าเริ่มต้นเป็น -1 ซึ่งหมายความว่าไม่มีค่าดังกล่าวอยู่
เหตุใดจึงเป็น O(n)
แต่ละดัชนีถูก ใส่หนึ่งครั้งและนำออกหนึ่งครั้ง แม้จะมีลูป while อยู่ด้านใน งานรวมตลอดการไล่ตรวจก็ยังมีเวลาเป็นเชิงเส้น
สลับเพื่อหาสมาชิกที่เล็กกว่าถัดไป
ต้องการหาสมาชิกที่เล็กกว่าถัดไปใช่หรือไม่ ให้รักษาสแตกให้ เรียงจากน้อยไปมาก โดยเปลี่ยนการเปรียบเทียบจากมากกว่าเป็นน้อยกว่า
while stack and nums[i] < nums[stack[-1]]:รูปแบบ ไม่ใช่กลเม็ด
การสอบถามช่วง ราคาหุ้น และพื้นที่ของฮิสโตแกรมล้วนนำแนวคิดนี้กลับมาใช้ สแตกแบบ โมโนโทน เป็นรูปแบบหลักในการแข่งขันที่ควรจดจำ
ตรวจสอบอย่างรวดเร็ว
คุณแก้ปัญหาสมาชิกที่มากกว่าถัดไปด้วยสแตกแบบโมโนโทน เหตุใดเวลารวมจึงเป็นเชิงเส้น
สรุป: การไล่ครั้งเดียวได้หลายคำตอบ
คุณใช้ สแตกแบบโมโนโทน ของดัชนีที่เรียงจากมากไปน้อย เพื่อหาสมาชิกที่มากกว่าถัดไปในเวลา O(n) รูปแบบนี้ช่วยแก้ปัญหาเกี่ยวกับช่วงได้อีกมากมาย 🚀
คำถามที่พบบ่อย
บทเรียน “สแตกโมโนโทน: สมาชิกที่มากกว่าถัดไป” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “สแตกโมโนโทน: สมาชิกที่มากกว่าถัดไป” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “สแตกโมโนโทน: สมาชิกที่มากกว่าถัดไป”
ตอบคำถามช่วงได้ในการวนผ่านรอบเดียว คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “สแตกโมโนโทน: สมาชิกที่มากกว่าถัดไป” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- สแตกสำหรับจับคู่วงเล็บ
- สแตกโมโนโทน: สมาชิกที่มากกว่าถัดไป
- คิวและ collections.deque
- ค่าสูงสุดในหน้าต่างเลื่อนด้วยดีค