Python程式：查詢獲利所需的最少天數

假設我們有一個價格列表，按時間順序表示公司每日股票市場價格。我們必須找到一個相同長度的列表，其中索引i處的數值表示我們必須等待的最少天數才能獲利。如果沒有獲利的方法，則該值為0。

因此，如果輸入類似於prices = [4, 3, 5, 9, 7, 6]，則輸出將為[2, 1, 1, 0, 0, 0]

為了解決這個問題，我們將遵循以下步驟

• ans := 一個與prices大小相同的列表，並填充0
• q := 一個新的列表
• 對於prices中的每個索引i和價格p，執行以下操作：
  • 當q不為空且p > q的最後一項的第二個值時，執行以下操作：
    • j := q的最後一項的第一個元素
    • ans[j] := i - j
    • 從q中刪除最後一項
  • 在q的末尾插入(i, p)
• 返回ans

讓我們看看下面的實現，以便更好地理解

示例

線上演示

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]

Arnab Chakraborty

更新於：2020年11月26日

200 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習