请根据每日 气温 列表 temperatures ,请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高,请在该位置用 0 来代替。
解法一:题意就是找到比自己值大的下标的差。拿到当前值,循环往后找比自己大的数,并且该值的下标与当前值的下标之差。(超时)
class Solution: def dailyTemperatures(self, temperatures): length, result = len(temperatures),[] for index, v in enumerate(temperatures): cur_index = index index += 1 while index < length: if temperatures[index] > v: result.append(index - cur_index) break index += 1 else: result.append(0) return result
解法二:
用一个栈去存储未找到比自己的值的下标,一个列表存储结果集,如果找到就取更新结果集。找不到默认就是0.
代码
class Solution: def dailyTemperatures(self,temperatures): result, stack = [0] * len(temperatures),[] for index,v in enumerate(temperatures): # 有未找的,并且栈顶元素的下标所对应的值小于当前值,说明找到了比自己的数,去更新结果集 while stack and temperatures[stack[-1]] < v: result[stack.pop()] = index - stack[-1] # 没有找到,把该索引添加进去,继续往后找大的值 stack.append(index) return result