Chương trình tìm số ngày chờ đợi tối thiểu để kiếm lợi nhuận trong python

Giả sử chúng ta có một danh sách giá đại diện cho giá thị trường chứng khoán hàng ngày của một công ty theo trình tự thời gian. Chúng ta phải tìm một danh sách cùng độ dài trong đó giá trị tại chỉ mục i sẽ là số ngày tối thiểu chúng ta phải đợi cho đến khi kiếm được lợi nhuận. Nếu không có cách nào như vậy để tạo ra lợi nhuận, giá trị phải là 0.

Vì vậy, nếu đầu vào là giá =[4, 3, 5, 9, 7, 6], thì đầu ra sẽ là [2, 1, 1, 0, 0, 0]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• ans:=một danh sách có kích thước giống như giá cả và điền bằng 0
• q:=một danh sách mới
• đối với mỗi chỉ số i và giá p trong các giá, hãy thực hiện
  • trong khi q không trống và p> giá trị thứ hai của mục cuối cùng của q, thực hiện
    • j:=mục đầu tiên của phần tử cuối cùng của q
    • ans [j]:=i - j
    • xóa phần tử cuối cùng khỏi q
  • chèn (i, p) vào cuối q
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

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]