LeetCode #739 Daily Temperatures: รอวันอุ่นขึ้นด้วย stack หรือมองอุณหภูมิที่เป็นไปได้

ถ้าต้องบอกแต่ละวันว่าอีกกี่วันอากาศจะ อุ่นกว่าเดิม เราอาจเปิดปฏิทินแล้วไล่มองไปทางขวาทีละวัน แต่เมื่อมีข้อมูลถึง 100,000 วัน วิธีนั้นอาจตรวจคู่วันเกือบหมื่นล้านคู่ LeetCode #739 Daily Temperatures เป็นโจทย์ฝึกเลือกโครงสร้างข้อมูลให้เหมาะกับคำถามแบบ “เหตุการณ์ถัดไปที่ดีกว่า”

โจทย์ให้ array temperatures มี 1 ถึง 100,000 ค่า แต่ละค่าอยู่ระหว่าง 30 ถึง 100 และให้คืนจำนวนวันที่ต้องรอจนเจอวันที่อุณหภูมิ สูงกว่าอย่างเคร่งครัด หากไม่มีวันนั้นให้ตอบ 0 เช่น [73, 74, 75, 71, 69, 72, 76, 73] ได้ [1, 1, 4, 2, 1, 1, 0, 0] วันที่ร้อนเท่ากันยังไม่ถือว่าเจอคำตอบ

วิธี 1: เปิดปฏิทินไล่ทีละวัน

สำหรับวัน i เดินจาก i+1 ไปทางขวาจนเจอค่าที่สูงกว่า วิธีนี้อ่านง่ายและเป็น oracle ที่ดีสำหรับทดสอบวิธีเร็ว แต่กรณีอุณหภูมิเท่ากันหรือค่อย ๆ ลด จะเสียเวลา O(n²) พื้นที่เพิ่ม O(1) หากไม่นับ array คำตอบ ภายใต้ n=100,000 จึงไม่ใช่ default ที่ควรส่ง

วิธี 2: เก็บวันที่ยังรอคำตอบใน monotonic stack

อ่านจากซ้ายไปขวาและเก็บ index ของวันที่ยังไม่พบวันอุ่นกว่า โดยอุณหภูมิของ index ใน stack เรียงจากสูงไปต่ำหรือเท่ากัน เมื่อวันใหม่อุ่นกว่าวันบนสุด ก็เติมคำตอบ today - old_day แล้ว pop ต่อจนหยุด วันใหม่เข้ากองรอของตัวเอง เหมือนคิวฝากกระดาษถามคำถาม: วันอุ่นใหม่ช่วยตอบหลายใบพร้อมกันได้

แต่ละ index เข้ากองหนึ่งครั้งและออกได้อย่างมากหนึ่งครั้ง จึงใช้เวลา O(n) และพื้นที่เพิ่ม O(n) ในกรณีมีวันรอค้างมาก วิธีนี้เป็น best default ภายใต้ constraints ของโจทย์ เพราะรับค่าอุณหภูมิทั่วไปได้โดยไม่พึ่งขอบเขต 30–100 และไม่แก้ input ถ้าอ่านเป็น stream ก็ประมวลผลได้ทีละค่า แต่จะส่งคำตอบครบทุกตำแหน่งได้เมื่อรู้ว่า stream จบแล้ว

วิธี 3: ใช้ขอบเขตอุณหภูมิ 30–100

อ่านจากขวาไปซ้ายแล้วจำ index ล่าสุดที่พบสำหรับแต่ละอุณหภูมิในตาราง 71 ช่อง สำหรับวันปัจจุบัน มองเฉพาะช่องที่ สูงกว่า ค่านี้แล้วเลือก index ใกล้ที่สุด วิธีนี้ไม่ใช้ stack และพื้นที่ตารางเพิ่ม O(71) แต่ต้องตรวจมากสุด 70 ช่องต่อวัน เวลา O(71n) ซึ่งเป็น O(n) เมื่อขอบเขต 30–100 คงที่ ข้อแลกเปลี่ยนคือ constant factor สูงและใช้ไม่ได้ตรง ๆ หากโจทย์ขยายอุณหภูมิเป็นค่าจำนวนเต็มช่วงกว้าง

from itertools import product
import unittest


def wait_brute(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    for i, current in enumerate(temperatures):
        for j in range(i + 1, len(temperatures)):
            if temperatures[j] > current:
                answer[i] = j - i
                break
    return answer


def wait_stack(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    pending: list[int] = []
    for today, current in enumerate(temperatures):
        while pending and current > temperatures[pending[-1]]:
            old_day = pending.pop()
            answer[old_day] = today - old_day
        pending.append(today)
    return answer


def wait_by_temperature(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    next_day: list[int | None] = [None] * 101
    for day in range(len(temperatures) - 1, -1, -1):
        current = temperatures[day]
        candidates = (next_day[warmer] for warmer in range(current + 1, 101))
        nearest = min((x for x in candidates if x is not None), default=None)
        if nearest is not None:
            answer[day] = nearest - day
        next_day[current] = day
    return answer


class DailyTemperaturesTests(unittest.TestCase):
    def test_examples_and_edges(self):
        cases = [
            ([73, 74, 75, 71, 69, 72, 76, 73], [1, 1, 4, 2, 1, 1, 0, 0]),
            ([30], [0]), ([30, 30, 30], [0, 0, 0]),
            ([100, 90, 80], [0, 0, 0]), ([30, 50, 40, 50, 100], [1, 3, 1, 1, 0]),
        ]
        for solve in (wait_brute, wait_stack, wait_by_temperature):
            for values, expected in cases:
                with self.subTest(method=solve.__name__, values=values):
                    self.assertEqual(solve(values), expected)

    def test_small_inputs_against_brute(self):
        for length in range(1, 6):
            for values in product((30, 31, 32), repeat=length):
                sample = list(values)
                expected = wait_brute(sample)
                self.assertEqual(wait_stack(sample), expected)
                self.assertEqual(wait_by_temperature(sample), expected)


if __name__ == "__main__":
    unittest.main()

Decision table

เงื่อนไข	ไล่ทีละวัน	Stack	ตารางอุณหภูมิ
Input เล็กและเน้นอ่านง่าย	สั้นที่สุด	ต้องเข้าใจ invariant	ต้องรู้ช่วงค่า
Input ใหญ่ใกล้ 100,000	ช้า O(n²)	เหมาะสุด O(n)	O(71n) ทำได้แต่ตรวจหลายช่อง
Memory จำกัด	O(1) เพิ่ม	O(n)	O(71) เพิ่ม
Input เรียงขึ้นแล้ว	O(n) ในกรณีนี้	O(n)	ตรวจช่วงค่า
รับค่าแบบ streaming	ต้องรออนาคต	เก็บ index ค้างและตอบเมื่อเจอวันอุ่น	ต้องอ่านจากขวา จึงต้องเก็บครบ
ห้ามแก้ input	ได้	ได้	ได้
อุณหภูมิไม่จำกัด 30–100	ได้	ได้	ต้องเปลี่ยนโครงสร้าง

Edge cases และข้อแลกเปลี่ยน

วันเดียวตอบ 0; อุณหภูมิเท่ากันทั้งหมดตอบศูนย์ทั้งหมด เพราะ > ไม่ใช่ >=; วันที่ร้อนสุด 100 ไม่มีค่าที่สูงกว่าใน constraints; และวันอุ่นอาจอยู่ไกลหลายวันหลังช่วงเย็นชั่วคราว โค้ดด้านบนไม่เปลี่ยน temperatures เลย Tests รันทั้งตัวอย่างสำคัญและชุดข้อมูลสั้นทุกแบบจากค่า 30, 31, 32 เพื่อเทียบสองวิธีเร็วกับวิธีตรงไปตรงมา

Recap

• แยก “สูงกว่า” ออกจาก “เท่ากัน” ก่อนเขียนเงื่อนไข
• ใช้วิธีไล่ทีละวันเป็นจุดตรวจความถูกต้องสำหรับ input เล็ก
• ใช้ stack เป็น default เมื่อ input ใหญ่และช่วงค่าอาจเปลี่ยน
• ใช้ตาราง 71 ช่องเมื่อจำกัด memory และเชื่อถือช่วง 30–100 ได้จริง