-
Notifications
You must be signed in to change notification settings - Fork 11
/
DailyTemperatures.java
46 lines (33 loc) · 1.26 KB
/
DailyTemperatures.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.Stack;
public class DailyTemperatures {
/*单调栈: for循环入栈 什么情况下出栈 : 找到了比栈顶元素大的数的时候出栈 栈里面存储的是下标 当前下标-栈下标就是距离(隔了几天)*/
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] array = new int[n];
Stack<Integer> stack = new Stack<Integer>();
// int prev = 0;
for (int i = 0; i < n; i++) {
while (!stack.isEmpty()&& temperatures[stack.peek()]<temperatures[i]){
int prev = stack.pop();
array[prev] = i - prev;
}
stack.push(i);
}
return array;
}
/*暴力解法 : 考虑问题时候可以先暴力解法 再考虑优化 ,或者其他的数据结构来优化*/
public int[] dailyTemperaturesTwo(int[] temperatures) {
// 暴力解法
int n = temperatures.length;
int[] array = new int[n];
for (int i = 0; i < n; i++) {
for (int j = i+1; j <n ; j++) {
if (temperatures[j] >temperatures[i]){
array[i] = j-i;
break;
}
}
}
return array;
}
}