파이썬에서 수익을 내기 위해 기다려야 하는 최소 일수를 찾는 프로그램

회사의 일일 주식 시장 가격을 시간 순서대로 나타내는 가격 목록이 있다고 가정합니다. 인덱스 i의 값이 수익을 낼 때까지 기다려야 하는 최소 일수가 되는 동일한 길이의 목록을 찾아야 합니다. 수익을 낼 수 있는 방법이 없다면 값은 0이어야 합니다.

따라서 입력이 가격 =[4, 3, 5, 9, 7, 6]과 같으면 출력은 [2, 1, 1, 0, 0, 0]

이 문제를 해결하기 위해 다음 단계를 따릅니다.

• ans :=가격과 동일한 크기의 목록으로 0으로 채움
• q :=새 목록
• 가격의 각 지수 i와 가격 p에 대해 다음을 수행합니다.
  • q가 비어 있지 않고 p> q의 마지막 항목의 두 번째 값인 동안 do
    • j :=q의 마지막 요소의 첫 번째 항목
    • ans[j] :=i - j
    • q에서 마지막 요소 삭제
  • q 끝에 (i, p) 삽입
• 반환

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시

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))

입력

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

출력

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