โจทย์: Daily Temperatures
ให้รายการอุณหภูมิรายวัน T ต้องส่งคืนรายการที่แต่ละวันบอกว่า ต้องรออีกกี่วันจึงจะได้อุณหภูมิสูงกว่า** หากไม่มีวันในอนาคตที่อุณหภูมิสูงกว่า ให้เก็บ 0
ตัวอย่าง: T = [73, 74, 75, 71, 69, 72, 76, 73]
ผลลัพธ์: [1, 1, 4, 2, 1, 1, 0, 0]
อธิบาย: วันที่ 0 (73) รอ 1 วัน ได้ 74 | วันที่ 2 (75) รอ 4 วัน ได้ 76 | วันที่ 6-7 ไม่มีวันร้อนกว่า → 0
อัลกอริทึม: Monotonic Stack (สแท็กแบบเดี่ยว)
- สร้างอาร์เรย์
ansขนาดเท่าTเติม 0 ทั้งหมด - สร้างสแท็กเก็บ index ของวันที่ยังไม่เจออุณหภูมิสูงกว่า
- วนลูป
iจาก 0 ถึง n-1:- ในขณะที่สแท็กไม่ว่าง และ
T[i] > T[stack.top()]:- pop index ออกจากสแท็ก
ans[index] = i - index(จำนวนวันที่รอ)
- push
iเข้าสแท็ก
- ในขณะที่สแท็กไม่ว่าง และ
- ส่งคืน
ans
สแท็กจะเก็บ index ของวันที่อุณหภูมิ ลดลงเรื่อยๆ** (monotonic decreasing) เมื่อเจออุณหภูมิสูงกว่า จะ pop ออกและคำนวณระยะห่าง
ตัวอย่างโค้ด Python
class Solution:
def dailyTemperatures(self, T):
ans = [0] * len(T)
stack = [] # เก็บ index
for i in range(len(T)):
# ในขณะที่อุณหภูมิวันนี้สูงกว่าวันที่เก็บในสแท็ก
while stack and T[i] > T[stack[-1]]:
idx = stack.pop()
ans[idx] = i - idx
stack.append(i)
return ans
# ทดสอบ
ob = Solution()
print(ob.dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# Output: [1, 1, 4, 2, 1, 1, 0, 0]
Input
[73, 74, 75, 71, 69, 72, 76, 73]
Output
[1, 1, 4, 2, 1, 1, 0, 0]
ความซับซ้อน (Complexity)
- เวลา: O(n) - แต่ละ index ถูก push และ pop สูงสุด 1 ครั้ง
- พื้นที่: O(n) - สแท็กเก็บ index สูงสุด n ตัว
หมายเหตุ: โค้ดต้นฉบับใช้ while i < len(T) และจัดการสแท็กแบบ manual ซึ่งซับซ้อนกว่าจำเป็น โค้ดข้างต้นใช้ for loop แบบ Pythonic และสแท็ก list ธรรมดา
