มีราคาหุ้นรายวัน หาวันที่ต้องรอขั้นต่ำจากวัน i จนทำกำไรได้ (ราคาสูงกว่า) ถ้าไม่มีให้ 0
เช่น prices=[4,3,5,9,7,6] ให้ [2,1,1,0,0,0]
ขั้นตอนการแก้ปัญหา
- ใช้ Monotonic Stack เก็บ (index, price) เรียงราคาลดลง
- วนอ่านราคา: ขณะราคาปัจจุบัน > ราคาบนสุด stack ให้ pop และคำนวณวันต่าง
- Push ราคาปัจจุบันเข้า stack
ตัวอย่างโค้ด
class Solution:
def solve(self, prices):
ans = [0]*len(prices)
q = []
for i,p in enumerate(prices):
while q and p > q[-1][1]:
j = q[-1][0]
ans[j] = i - j
q.pop()
q.append((i,p))
return ans
ob = Solution()
prices = [4,3,5,9,7,6]
print(ob.solve(prices))
อินพุต
[4, 3, 5, 9, 7, 6]
เอาต์พุต
[2, 1, 1, 0, 0, 0]
