杭州市做外贸网站的公司,led论坛网站建设,做技术开发的网站,重庆建设摩托车股份有限公司官网题目描述 给定一个整数数组 temperatures #xff0c;表示每天的温度#xff0c;返回一个数组 answer #xff0c;其中 answer[i] 是指对于第 i 天#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升高#xff0c;请在该位置用 0 来代替。
解析 每次往栈中…题目描述 给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
解析 每次往栈中添加下标如果遇到比栈顶元素对应的温度高说明找到了栈顶的温度出栈并入栈当前温度。
public int[] dailyTemperatures(int[] temperatures) {int[] res new int[temperatures.length];DequeInteger s new LinkedList();s.push(0);for(int i 1; i temperatures.length; i) {while (!s.isEmpty() temperatures[s.peek()] temperatures[i]) {int pre s.pop();res[pre] i - pre;}s.push(i);}return res;}时间消耗最少的方式是动态规划从后往前遍历
如果第 i1 天的温度大于第 i 天的温度那么 dp[i] 1。如果第 i1 天的温度不大于第 i 天的温度那么查看 dp[i1] 如果 dp[i1] 是非零的说明从第 i1 天开始有一个已知的更热的天在 i1 dp[i1]。接下来检查那一天的温度是否高于第 i 天 如果是dp[i] 就是 1 dp[i1]。如果不是继续向后查看直到找到更热的一天或者查看到数组的尽头。
public int[] dailyTemperatures(int[] temperatures) {int ntemperatures.length;int[] dpnew int[n];for(int in-2;i0;i--){int ji1;while(jn temperatures[j]temperatures[i] dp[j]!0){jdp[j];}if(jn temperatures[j]temperatures[i]){dp[i]j-i;}}return dp;}虽然从此题提交的结果来看动态规划耗时更短但是使用栈最好最坏的复杂度都是O(n)而使用动态规划最好为O(n)最坏是O(n^2)因此实际开发还是建议使用栈的方式来解决问题。
