力扣735
https://leetcode-cn.com/problems/daily-temperatures/submissions/
自从上次做了最大矩形单调栈题目之后，最近笔试见了两题单调栈的题目了，心理作用？？赶紧补吧…
题目描述的不是很清楚（可以看英文版比较明白），总之，是说往后找到比当前大的（温度高的），然后记录下标距离。
很显然是单调栈的题目：”往后找到第一个”这样的字样
思路也比较简单：
- 往后找第一个比当前大的，因此采用递减栈。
- 栈中记录下标（因为要求的是下标差而且通过下标可以直接在T[i]中得出值作比较反之则困难，好多单调栈的题目都是这样记录的）
- 遇到比栈顶大则记录当前与栈顶元素的距离，出栈，循环直至满足递减栈
- 当前元素入栈。
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
| public class seven_three_nine_每日温度 {
@Test
public void test(){
int[] T = {73, 74, 75, 71, 69, 72, 76, 73};
int[] res = dailyTemperatures(T);
System.out.println(Arrays.toString(res));
}
public int[] dailyTemperatures(int[] T) {
int[] res = new int[T.length];
if (T == null || T.length == 0) return res;
Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(0);
for (int i = 1; i < T.length; i++) {
if (T[i] <= T[deque.peekLast()]){
deque.offerLast(i);
}else {
while (deque.size() != 0 && T[i] > T[deque.peekLast()]){
Integer beginIndex = deque.pollLast();
res[beginIndex] = i - beginIndex;
}
deque.offerLast(i);
}
}
return res;
}
}
|
ps：栈用Stack也是可以的，具体我在博客中有记录，双端队列的速度理论上会比Vector的子类Stack快
其他单调栈系列题可以点这里
