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].
分析
给定一个数组代表每天的气温，查找多少天之后天气比今天更暖和。首先，想到了暴力算法，如下，
- 遍历 T
- 对于第 i 个元素，另 j = i，从 i 开始往后寻找比 T[i] 大的元素，如果找到则
j - i为第 i 号元素的目标值 - 重复步骤 2 直到最后一位
给定数组为降序排列时，暴力算法复杂度为 O(n^2)，数组的长度在 [1, 30000]，暴力算法可能会超时。迫于没有想到更好的解题思路，只能对暴力算法先做优化，如果数组是升序的，算法复杂都是 O(n)，所以很乐观，主要考虑优化降序的部分。
考虑如下情况，数组先增后降，
下降转折点到末尾数组元素单调递减，因此每个元素后面都不会有大于他们的元素
如果单调递减后有转折点，那么单调递减的部分元素可能会存在