Pythonで利益を上げるために待つ最小日数を見つけるプログラム

会社の毎日の株式市場価格を時系列で表す価格のリストがあるとします。インデックスiの値が、利益を上げるまで待たなければならない最小日数となる同じ長さのリストを見つける必要があります。利益を上げるそのような方法がない場合、値は0である必要があります。

したがって、入力がprices =[4、3、5、9、7、6]のような場合、出力は[2、1、1、0、0、0]

これを解決するには、次の手順に従います。

• ans：=価格と同じサイズのリストで、0を入力します
• q：=新しいリスト
• 価格の各インデックスiと価格pについて、
  • qが空ではなく、p> qの最後の項目の2番目の値である場合、
    • 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]