题目描述
Leetcode 739 本题考察了栈的使用。题目输入是一段温度值列表，然后返回一个列表。这个列表包含了输入列表中每一天还有多少天温度升高。如果未来没有升高的情况，则输入 0。
# Example1:
# Input: T = [73, 74, 75, 71, 69, 72, 76, 73]
# Output: [1, 1, 4, 2, 1, 1, 0, 0]
# 比如 index=0 这天温度为 73 度，index=1，这天为 74 度。
# 所以针对 index=0 这天，还需要 1 天温度会升高。
# 对于 index=2 这天，还需要 4 天才可以温度升高。
题目分析
通常的做法是从某一位置开始依次和该位置之后的温度进行比较，但这样就会出现冗余的情况。
拿 index=2 的温度来说，会和 71,69,72,76 依次做比较。但实际上经过此次比较，71,69 已
经找到比它本身温度高的答案了，复杂度为 O(N^2)
可以使用栈进行保存，栈里面保存的是当前栈顶元素的下标。而当前遍历元素的下标减去栈顶元素的
下标就是所需要经历的天数。每个元素最多被弹出和压入栈一次，因此为 O(N).
# Question: Daily Temperatures
# Given a list of daily temperatures T, return a list such that, for each day in
# the input, tells you how many days you would have to wait until a warmer
# temperature. If there is no future day for which this is possible, put 0
# instead.
# Example1:
# T = [73, 74, 75, 71, 69, 72, 76, 73]
# [1, 1, 4, 2, 1, 1, 0, 0]
# Note:
# the length of temperatures will be in the range [1, 30000]
# Each temperature will be an integer in the range [30, 100]
class Solution(object):
def dailyTemperatures(self, T):
"""
:type T: List[int]
:rtype: List[int]
"""
stack = []
stack_sky = [0] * len(T)
for index, element in enumerate(T):
if stack.__len__() > 0:
tem = T[stack[-1]]
while stack and element > tem:
stack_sky[stack[-1]] = index - stack[-1]
stack.pop()
if stack.__len__() > 0:
tem = T[stack[-1]]
stack.append(index)
return stack_sky
if __name__ == '__main__':
example_list_1 = [73, 74, 75, 71, 69, 72, 76, 73]
example_list_2 = [89, 62, 70, 58, 47, 47, 46, 76, 100, 70]
solution = Solution()
print(solution.dailyTemperatures(example_list_2))