题目描述
分析
题意: 输入
[30,31,34,29,30,35]，输出[1,1,3,1,1,0]，分析:从30出发，找到第一个比30大的数，即31，两个数下标差1，即输出第一个是1，再比如35，但是后面没有数了，即输出最后一个数0
1. 暴力
2. 队列
代码实现
public enum Q739 {
instance;
// O(n^2)
public int[] dailyTemperatures(int[] T) {
if(T==null||T.length==0)return null;
for(int i=0;i<T.length;i++){
int count=0;
// 若后面的数都小于当前的数，则count=0
int letterCount=0;
for(int j=i+1;j<T.length;j++){
if(T[i]>=T[j]){
letterCount++;
}else {
// 若有大于当前数的,则两个数之和
if(j-i!=letterCount){
count+=++letterCount;
}
break;
}
}
T[i]=count;
}
return T;
}
// 官方题解 O(n)
public int[] dailyTemperatures1(int[] T) {
int length = T.length;
int[] ans = new int[length];
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < length; i++) {
int temperature = T[i];
while (!stack.isEmpty() && temperature > T[stack.peek()]) {
int prevIndex = stack.pop();
ans[prevIndex] = i - prevIndex;
}
stack.push(i);
}
return ans;
}
public static void main(String[] args) {
// assert [1,1,4,2,1,1,0,0]
SystemUtil.print(Q739.instance.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73}));
// assert [2,1,1,4,3,2,1,0]
SystemUtil.print(Q739.instance.dailyTemperatures(new int[]{44, 33, 45, 49, 43, 40, 39, 52}));
// assert [1,1,4,2,1,1,0,0]
SystemUtil.print(Q739.instance.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73}));
SystemUtil.print(Q739.instance.dailyTemperatures1(new int[]{73, 74, 75, 71, 69, 72, 76, 73}));
}
}
