题目大意：
每日温度
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=739
解题思路分析：
这道题目实际上求的是距离每一位右侧最近的大于它的数字与他的距离差。Leetcode上这一类的题目很多，记得两周前的周赛刚做过一道类似的题目：LEETCODE 1475. Final Prices With a Special Discount in a Shop 解题思路分析。
解题时，首先求出每一位数字右侧与之相邻的最近大数下标，并记录在数组leftBig[]中。默认距离每一位最近的大数下标为本身，即leftBig[i]=i。由于最后一位右侧没有元素，因此我们从数组的倒数第二位开始向前循环。对于当前位置i，如果temperatures[i+1]>temperatures[i]，那么距离当前元素最近的大数下标为i+1，即leftBig[i]=i+1。反之，如果temperatures[i+1]<=temperatures[i]，我们可以查看距离i+1最近的大数下标leftBig[i+1]，如果该数字仍小于当前数字，继续查看距离该数字最近的大数下标，直到找到比当前数字大的数值位置。另外，当leftBig[j]=j时，代表这之后没有再大于该数字的值，因此leftBig[i]=i。
有了leftBig数组，这与我们想要的结果仅差一步之遥，leftBig[i]代表距离下标i右侧最近 的大数下标，那么与该大数的距离即为：leftBig[i]-i。
实现代码：
public int[] dailyTemperatures(int[] T) {
int[] nextBig = new int[T.length];
for(int i=0;i<T.length;i++) nextBig[i]=i;
for(int i=T.length-2;i>=0;i--){
if(T[i+1]>T[i]){
nextBig[i]=i+1;
}else{
int nextIndex=i+1;
while(T[i]>=T[nextIndex]&&nextIndex!=nextBig[nextIndex]){
nextIndex=nextBig[nextIndex];
if(T[nextIndex]>T[i]){
nextBig[i]=nextIndex;
break;
}
}
}
}
for(int i=0;i<T.length;i++) nextBig[i]=nextBig[i]-i;
return nextBig;
}本题解法执行时间为4ms。
Runtime: 4 ms, faster than 96.73% of Java online submissions for Daily Temperatures.
Memory Usage: 47.4 MB, less than 60.93% of Java online submissions for Daily Temperatures.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-739-daily-temperatures-解题思路分析/