On this page

ข้อ 75 · LC901 Online Stock Span (ช่วงราคาหุ้นออนไลน์) 🟡

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

ออกแบบ StockSpanner ที่ return span ของราคาแต่ละวัน ด้วย stack เก็บคู่ (price, span) ที่ยุบไว้แล้ว

โจทย์ (LC901): ให้ออกแบบ algorithm ที่รวบรวมราคาหุ้นรายวัน (daily price quotes) แล้ว return span ของราคาหุ้นในวันปัจจุบัน โดย span ของวันหนึ่งคือจำนวนวันติดต่อกันมากที่สุด (เริ่มนับจากวันนั้นย้อนกลับไป) ที่ราคาหุ้นน้อยกว่าหรือเท่ากับราคาของวันนั้น ให้ implement class StockSpanner ที่มี constructor StockSpanner() และ method next(price) ซึ่งคืนค่า span ของราคาวันนี้

Example 1

Input:: เรียก next(price) ตามลำดับด้วยราคา 100, 80, 60, 70, 60, 75, 85
Output:: 1, 1, 1, 2, 1, 4, 6
Explanation:: วันราคา 70 ย้อนไปมี 60 ที่ไม่เกิน 70 รวมวันนี้เป็น 2 วัน วันราคา 75 ย้อนไปมี 60, 70, 60 ที่ไม่เกิน 75 รวมวันนี้เป็น 4 วัน วันราคา 85 ย้อนไปครอบคลุมถึง 75, 60, 70, 60, 80 (ไม่เกิน 85) รวมวันนี้เป็น 6 วัน

Constraints (ข้อจำกัด)

1 <= price <= 10^5
เรียก next ได้มากสุด 10^4 ครั้ง

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

ข้อนี้ใช้ monotonic stack แบบเก็บคู่ (price, span) โดยราคาเรียง decreasing (ลดลง) จากล่างขึ้นบน แนวคิดคือแทนที่จะย้อนนับราคาทีละวันทุกครั้ง เราเก็บผลลัพธ์ span ที่ยุบไว้แล้วใน stack

วิธีตรงไปตรงมาคือเก็บราคาทั้งหมด แล้วทุกครั้งที่ next ย้อนนับถอยหลังจนเจอราคาที่แพงกว่า ซึ่งเป็น O(n) ต่อการ call (เรียก) และช้าเมื่อเรียกบ่อย ๆ การเก็บ (price, span) ใน stack ทำให้ยุบวันที่ราคาไม่เกินวันนี้รวมกันได้ในทีเดียว

เก็บ stack ของคู่ (price, span) ไว้ใน __init__
ใน next(price): initialize span = 1 (อย่างน้อยนับวันนี้)
ขณะที่ stack ไม่ว่างและราคายอด stack น้อยกว่าหรือเท่ากับ price: pop ออกมาแล้วบวก span ของมันเข้ากับ span ปัจจุบัน
push (price, span) เข้า stack แล้ว return span

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

เงื่อนไขต้องเป็น <= (น้อยกว่าหรือเท่ากับ) เพราะโจทย์นับวันที่ราคาเท่ากันด้วย ถ้าใช้ < จะนับ span ผิดเมื่อมีราคาซ้ำ และต้องเก็บ span ที่ยุบไว้ในคู่ ไม่ใช่เก็บแค่ราคา ไม่งั้นจะเสียข้อมูลที่ยุบไปแล้ว

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

จำลอง prices = [100, 80, 60, 70, 60, 75, 85] (stack เก็บคู่ price,span)

price	stack ก่อน	ยุบ (span รวม)	span	stack หลัง
100	[]	-	1	[(100,1)]
80	[(100,1)]	-	1	[(100,1),(80,1)]
60	[(100,1),(80,1)]	-	1	[...,(60,1)]
70	[...,(60,1)]	pop(60,1)	2	[(100,1),(80,1),(70,2)]
60	[...,(70,2)]	-	1	[...,(70,2),(60,1)]
75	[...,(70,2),(60,1)]	pop(60,1),(70,2)	4	[(100,1),(80,1),(75,4)]
85	[(100,1),(80,1),(75,4)]	pop(75,4),(80,1)	6	[(100,1),(85,6)]

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

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

class StockSpanner:
    def __init__(self):
        # stack เก็บคู่ (ราคา, span ของราคานั้น) ราคาลดจากล่างขึ้นบน
        self.stack = []

    def next(self, price):
        span = 1   # อย่างน้อยนับวันนี้เอง 1 วัน
        # ยุบทุกวันก่อนหน้าที่ราคาไม่เกินราคาวันนี้ รวม span เข้ามา
        while self.stack and self.stack[-1][0] <= price:
            _, prev_span = self.stack.pop()
            span += prev_span
        self.stack.append((price, span))
        return span

spanner = StockSpanner()
prices = [100, 80, 60, 70, 60, 75, 85]
print([spanner.next(p) for p in prices])
# [1, 1, 1, 2, 1, 4, 6]

Output

[1, 1, 1, 2, 1, 4, 6]

แทนที่จะย้อนนับราคาทีละวันทุกครั้ง (ซึ่งเป็น O(n) ต่อการ call) เราเก็บผลลัพธ์ที่ยุบไว้แล้วใน stack ในรูปคู่ (price, span) เมื่อราคาวันใหม่มากกว่าหรือเท่ากับราคายอด stack แปลว่าวันนั้น (และ span ที่มันเก็บไว้แล้ว) ทั้งหมดถูกครอบด้วยวันนี้ เราจึง pop แล้วบวก span ของมันสะสมเข้ากับ span ของวันนี้ ทำแบบนี้ไปเรื่อย ๆ จนเจอวันที่ราคาแพงกว่า ซึ่งเป็นขอบเขตซ้ายของช่วง

จุดที่ต้องระวังคือเงื่อนไขต้องเป็น <= (น้อยกว่าหรือเท่ากับ) เพราะโจทย์นับวันที่ราคาเท่ากันด้วย ถ้าใช้ < เฉย ๆ จะนับ span ผิดเมื่อมีราคาซ้ำ อีกจุดคือต้องเก็บ span ที่ยุบไว้ในตัว ไม่ใช่เก็บแค่ราคา ไม่งั้นจะเสียข้อมูลที่ยุบไปแล้ว

Time เฉลี่ย O(1) ต่อการ call next หนึ่งครั้ง (amortized) เพราะแต่ละราคาถูก push และ pop อย่างละครั้งตลอดอายุการใช้งาน · Space O(n) กรณีแย่สุด (ราคา decreasing เรื่อย ๆ) stack เก็บทุกวัน

💡 สรุป pattern

เมื่อต้องนับย้อนหลังแบบ streaming และอยากรวมผลที่คำนวณแล้ว ให้เก็บคู่ (ค่า, ผลที่ยุบไว้) ใน monotonic stack แล้วยุบตอน pop — ได้ amortized O(1) ต่อครั้ง