Python每日温度

假设我们有一列每日温度T，我们需要返回一个列表，对于输入中的每一天，显示我们需要等待多少天才能等到更高的温度。如果未来没有更高温度的一天，则存储0。例如，如果T = [73, 74, 75, 71, 69, 72, 76, 73]，输出将是[1, 1, 4, 2, 1, 1, 0, 0]。

为了解决这个问题，我们将遵循以下步骤：

• ans := 一个与T大小相同的数组，并将其填充为0
• 定义一个栈，并将0插入栈中，i := 1
• 当i < T的长度时
  • 当栈元素个数不为0且T[i] > T[栈顶元素]时
    • index := 栈顶元素
    • ans[index] := i – index
    • 从栈中删除顶元素
  • 如果栈的长度为0或T[i] <= T[栈顶元素]
    • 将i插入栈中
  • i增加1
• 返回ans

示例(Python)

让我们看看下面的实现来更好地理解：

 在线演示

class Solution(object):
   def dailyTemperatures(self, T):
      ans = [0 for i in range(len(T))]
      stack = []
      stack.append(0)
      i=1
      while i <len(T):
         while len(stack) and T[i]>T[stack[-1]]:
            index = stack[-1]
            ans[index] = i-index
            stack.pop()
         if not len(stack) or T[i]<=T[stack[-1]]:
            stack.append(i)
         i+=1
      return ans
ob1 = Solution()
print(ob1.dailyTemperatures([73,74,75,71,69,72,76,73]))

输入

[73,74,75,71,69,72,76,73]

输出

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

Arnab Chakraborty

更新于：2020年4月29日

845 次浏览

开启您的职业生涯

通过完成课程获得认证

开始学习