网站定制合同和模版的区别,怎么做自己的发卡网站,网站建设专业培训,wordpress 登陆注册题目
请根据每日 气温 列表 temperatures #xff0c;重新生成一个列表#xff0c;要求其对应位置的输出为#xff1a;要想观测到更高的气温#xff0c;至少需要等待的天数。如果气温在这之后都不会升高#xff0c;请在该位置用 0 来代替。
示例 1:
输入: temperatures…题目
请根据每日 气温 列表 temperatures 重新生成一个列表要求其对应位置的输出为要想观测到更高的气温至少需要等待的天数。如果气温在这之后都不会升高请在该位置用 0 来代替。
示例 1:
输入: temperatures [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]示例 2:
输入: temperatures [30,40,50,60]
输出: [1,1,1,0]示例 3:
输入: temperatures [30,60,90]
输出: [1,1,0]提示
1 temperatures.length 10530 temperatures[i] 100 注意本题与主站 739 题相同 力扣LeetCode官网 - 全球极客挚爱的技术成长平台
LCR 038. 每日温度 - 力扣LeetCode
题解
思路一暴力解法因为温度是从30-100.使用一个sum数组来存储所有出现的温度对应的距离当前元素最近的下标。从后向前遍历原始数组。sum[i]i表示温度sum[i]表示在原数组中的下标。因为是后序遍历的因此一定是出现在后面的更高温度。
代码
class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] sum new int[101];int[] ansnew int[temperatures.length];Arrays.fill(sum,Integer.MAX_VALUE);for(int itemperatures.length-1;i0;i--) {int indexInteger.MAX_VALUE;for(int jtemperatures[i]1;j101;j) {if(sum[j]index) {indexsum[j];}}if(indexInteger.MAX_VALUE) ans[i]index-i;//一定要记得-i因为是从i开始算第多少个温度更高sum[temperatures[i]]i;}return ans;}
}
思路二单调栈思想栈中存储下标栈中数据所代表的温度从栈底到栈顶是从高到低的从前向后遍历原始数组。栈不空时当有温度元素大于栈顶元素时取出栈顶元素更新ans[栈内index]代表的是还需要几天才升高当前index-栈内index温度小于栈顶或者栈空时直接入栈最后将所有的栈内残留ans[index]0。 代码
class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] ans new int[temperatures.length];DequeInteger stack new ArrayDequeInteger();for (int i 0; i length; i) {int temperature temperatures[i];while (!stack.isEmpty() temperature temperatures[stack.peek()]) {int prevIndex stack.pop();ans[prevIndex] i - prevIndex;}stack.push(i);}return ans;}
}
