要求
给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替
提示:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
思路
方法一:暴力解(超时)
遍历每一个元素,然后再从当前元素往后找比它大的,找到之后记录下他俩位置的差值,然后停止内层循环,如果没找到默认为0。
public int[] dailyTemperatures(int[] T) {
int length = T.length;
int[] res = new int[length];
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if (T[j] > T[i]) {
res[i] = j - i;
break;
}
}
}
return res;
}
方法二:栈
栈中存放的是数组元素的下标,元素入栈,遇到比栈顶元素大的数则栈顶元素出栈,当前元素下标减去出栈元素下标
public int[] dailyTemperatures(int[] T) {
Stack<Integer> stack = new Stack<>();
int[] ret = new int[T.length];
for (int i = 0; i < T.length; i++) {
while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
int idx = stack.pop();
ret[idx] = i - idx;
}
stack.push(i);
}
return ret;
}
方法三:做右往左遍历
public class LeetCode739 {
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
for (int i = res.length - 1; i >= 0; i--) {
int j = i + 1;
while (j < res.length){
if (temperatures[j] > temperatures[i]){
res[i] = j - i;
break;
}else if(res[j] == 0){
break;
}else {
j += res[j];
}
}
}
return res;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)