本文主要是介绍[LeetCode] 739. Daily Temperatures,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题:https://leetcode.com/problems/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].
题目大意
求数组中元素与下一个比它大的元素之间的距离,若没有距离设为0。
思路
动态规划,其实 觉得更像 贪心。
状态dp[i] :数组中元素与下一个比它大的元素之间的距离。
初始化:dp[Tlen-1] = 0;
状态转移:
设j = 1;若T[i]<T[i+j],则 dp[i] = j,否则,若dp[i+j] == 0,dp[i] = 0;
j = j + dp[i+j],继续上述操作。
class Solution {public int[] dailyTemperatures(int[] T) {int Tlen = T.length;int[] dp = new int[Tlen];for(int i = Tlen-2;i>=0;i--){int j = 1;while(T[i]>=T[i+j]){if(dp[i+j]==0){j = 0;break;}j = j + dp[i+j];}dp[i] = j;}return dp;}
}
这篇关于[LeetCode] 739. Daily Temperatures的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!