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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习