Chương trình tìm số ngày chờ đợi tối thiểu để có lãi cổ phiếu bằng Python

Cho danh sách prices giá cổ phiếu theo ngày. Với mỗi ngày i, tìm số ngày tối thiểu phải chờ để giá cao hơn (có lãi). Không có thì 0.

Ví dụ: [4,3,5,9,7,6] → [2,1,1,0,0,0].

Giải thuật

• Duyệt giá, dùng stack q lưu cặp (index, price) giảm dần.
• Khi giá hiện tại > giá đỉnh stack: pop, gán ans[j] = i - j.
• Push (i, p) vào stack.
• Phức tuyến O(n).

Ví dụ minh họa

class Solution:
    def solve(self, prices):
        ans = [0 for _ in 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))

Đầu vào

[4, 3, 5, 9, 7, 6]

Đầu ra

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