On this page

ข้อ 74 · LC739 Daily Temperatures (อุณหภูมิรายวัน) 🟡

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

คืนจำนวนวันที่ต้องรอจนเจอวันที่ร้อนกว่า ด้วย monotonic stack เก็บ index ของวันที่ยังรอ

โจทย์ (LC739): กำหนด array จำนวนเต็มชื่อ temperatures แทนอุณหภูมิรายวัน ให้ return array ชื่อ answer โดย answer[i] คือจำนวนวันที่ต้องรอหลังจากวันที่ i จึงจะเจอวันที่อุณหภูมิอุ่นกว่า (warmer) ถ้าไม่มีวันไหนในอนาคตอุ่นกว่าเลย ให้ answer[i] เป็น 0

Example 1

Input:: temperatures = [73,74,75,71,69,72,76,73]
Output:: [1,1,4,2,1,1,0,0]
Explanation:: วันแรก 73 วันถัดมา 74 ร้อนกว่าเลยตอบ 1 ส่วนวันที่ 76 ไม่มีวันไหนหลังจากนั้นร้อนกว่าจึงตอบ 0

Example 2

Input:: temperatures = [30,40,50,60]
Output:: [1,1,1,0]
Explanation:: อุณหภูมิเพิ่มขึ้นทุกวัน แต่ละวันจึงรอแค่ 1 วันก็เจอวันที่ร้อนกว่า ยกเว้นวันสุดท้ายที่ไม่มีวันไหนร้อนกว่าอีก

Example 3

Input:: temperatures = [30,60,90]
Output:: [1,1,0]
Explanation:: อุณหภูมิเพิ่มขึ้นต่อเนื่องล้วน แต่ละวันเจอวันร้อนกว่าในวันถัดไปทันที ยกเว้นวันสุดท้าย

Constraints (ข้อจำกัด)

1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100

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

ข้อนี้คือ next greater element (ตัวถัดไปที่มากกว่า) ในรูประยะห่าง ใช้ monotonic stack เก็บ index (ตำแหน่ง) ของวันที่ยังรอวันร้อนกว่า โดยอุณหภูมิเรียง decreasing (ลดลง) จากล่างขึ้นบนของ stack

วิธีตรงไปตรงมาคือแต่ละวัน iterate (วน) ดูวันข้างหน้าไปเรื่อย ๆ จนเจอวันที่ร้อนกว่า ซึ่งกรณีแย่สุดเป็น O(n^2) แต่ด้วย stack เราเก็บวันที่ยังไม่เจอคำตอบไว้ พอเจอวันที่ร้อนกว่ายอด stack ก็เคลียร์คำตอบให้วันเหล่านั้นทีเดียว iterate array รอบเดียวจบ

สร้าง answer ยาวเท่า array เติม 0 (0 = ไม่มีวันร้อนกว่า) และ stack ว่าง
iterate ทุกวัน i พร้อมอุณหภูมิ temp
ขณะที่ stack ไม่ว่างและ temp มากกว่าอุณหภูมิของวันที่ยอด stack: pop (ดึงออก) วันนั้น (prev_day) แล้วตั้ง answer[prev_day] = i - prev_day
push (ใส่) i เข้า stack แล้ววนต่อ สุดท้าย return answer

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

คำตอบต้องเป็นระยะห่าง i - prev_day (จำนวนวัน) ไม่ใช่อุณหภูมิหรือ index ดิบ และวันที่ยังค้างใน stack ตอนจบ loop คือวันที่ไม่มีวันร้อนกว่า ปล่อยให้เป็น 0 ตามค่าเริ่มต้นได้เลย

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

จำลอง temperatures = [73,74,75,71,69,72,76,73] (stack เก็บ index)

i	temp	stack ก่อน	pop & ตั้งคำตอบ	stack หลัง
0	73	[]	-	[0]
1	74	[0]	answer[0]=1	[1]
2	75	[1]	answer[1]=1	[2]
3	71	[2]	-	[2,3]
4	69	[2,3]	-	[2,3,4]
5	72	[2,3,4]	answer[4]=1, answer[3]=2	[2,5]
6	76	[2,5]	answer[5]=1, answer[2]=4	[6]
7	73	[6]	-	[6,7]

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

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

def daily_temperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n     # 0 = ไม่มีวันร้อนกว่าในอนาคต
    stack = []           # เก็บ index ของวันที่ยังรอวันร้อนกว่า
    for i, temp in enumerate(temperatures):
        # วันนี้ร้อนกว่ายอด stack ไหม ถ้าใช่คือคำตอบของวันนั้น
        while stack and temp > temperatures[stack[-1]]:
            prev_day = stack.pop()
            answer[prev_day] = i - prev_day   # ระยะห่างเป็นจำนวนวัน
        stack.append(i)
    return answer

print(daily_temperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]
print(daily_temperatures([30, 40, 50, 60]))  # [1, 1, 1, 0]
print(daily_temperatures([30, 60, 90]))      # [1, 1, 0]

Output

[1, 1, 4, 2, 1, 1, 0, 0]
[1, 1, 1, 0]
[1, 1, 0]

เรา iterate วันทีละวัน เก็บ index ของวันที่ยังไม่เจอวันร้อนกว่าไว้ใน stack โดย stack จะเรียงอุณหภูมิ decreasing จากล่างขึ้นบนเสมอ เมื่อวันปัจจุบันร้อนกว่าวันที่ยอด stack แปลว่าเราเพิ่งเจอวันร้อนกว่าของวันนั้นพอดี จึง pop ออกมาแล้วบันทึกระยะห่าง i - prev_day เป็นจำนวนวันที่ต้องรอ ทำซ้ำจนวันปัจจุบันไม่ได้ร้อนกว่ายอด stack แล้วค่อย push วันปัจจุบันเข้าไป

จุดสำคัญที่ทำให้เร็วคือแต่ละวันถูก push และ pop อย่างละครั้งเดียว จึงเป็น O(n) วันที่ยังค้างใน stack ตอนจบ loop คือวันที่ไม่มีวันร้อนกว่า answer ของมันคงเป็น 0 ตามค่าเริ่มต้น ไม่ต้องทำอะไรเพิ่ม

Time O(n) แต่ละ index push/pop อย่างละครั้ง · Space O(n) กรณีแย่สุด (อุณหภูมิ decreasing เรื่อย ๆ) stack เก็บทุก index

💡 สรุป pattern

เจอคำถามแนว 'อีกไกลแค่ไหนจะเจอตัวที่มากกว่า/น้อยกว่า' ให้นึกถึง monotonic stack เก็บ index แล้วเคลียร์คำตอบตอน pop — เปลี่ยน O(n^2) เป็น O(n)