Leetcode-739 Daily Temperatures

Description

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.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [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].

分析

给定一个数组代表每天的气温,查找多少天之后天气比今天更暖和。首先,想到了暴力算法,如下,

  1. 遍历 T
  2. 对于第 i 个元素,另 j = i,从 i 开始往后寻找比 T[i] 大的元素,如果找到则 j - i 为第 i 号元素的目标值
  3. 重复步骤 2 直到最后一位

给定数组为降序排列时,暴力算法复杂度为 O(n^2),数组的长度在 [1, 30000],暴力算法可能会超时。迫于没有想到更好的解题思路,只能对暴力算法先做优化,如果数组是升序的,算法复杂都是 O(n),所以很乐观,主要考虑优化降序的部分。

考虑如下情况,数组先增后降,

下降转折点到末尾数组元素单调递减,因此每个元素后面都不会有大于他们的元素

如果单调递减后有转折点,那么单调递减的部分元素可能会存在

本文标题:Leetcode-739 Daily Temperatures

文章作者:Syncher

发布时间:2019年08月04日 - 17:08

最后更新:2019年10月10日 - 18:10

原始链接:https://0x400.com/2019-08-04-lc-739-daily-temperatures.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。