Stock Span · Nhóm: Ngăn xếp & Hàng đợi
Với mỗi ngày, đếm số ngày liên tiếp gần nhất kể cả hôm nay có giá không vượt giá hôm nay bằng ngăn xếp đơn điệu giảm.
Ngăn xếp lưu chỉ số các ngày mà giá còn lớn hơn mọi ngày sau nó, giá giảm dần từ đáy lên đỉnh.
Khi giá hôm nay không nhỏ hơn đỉnh, pop đỉnh vì nó bị hôm nay che khuất.
Nhịp giá bằng khoảng cách tới ngày giá lớn hơn gần nhất còn lại trong ngăn xếp.
Mỗi ngày chỉ vào và ra ngăn xếp đúng một lần, đỉnh còn lại luôn là ngày giá lớn hơn gần nhất nên tính nhịp tức thì.
def stock_span(prices):
n = len(prices)
span = [0] * n
stack = [] # indices, prices decreasing
for i in range(n):
while stack and prices[stack[-1]] <= prices[i]:
stack.pop() # this day is masked by day i
prev = stack[-1] if stack else -1 # last day with a greater price
span[i] = i - prev
stack.append(i)
return span
Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.