382，每日温度的5种解题思路
People make mistakes. That's the very reason why they put rubbers on the ends of pencils.
人们都会犯错，这便是铅笔需要橡皮的原因。
问题描述
请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如
给定一个列表
[73, 74, 75, 71, 69, 72, 76, 73]
你的输出应该是
[1, 1, 4, 2, 1, 1, 0, 0]。
说明：
73的时候只需要等1天，温度是74比73大。
74的时候只需要等1天，温度是75比74大。
75的时候只需要等4天，温度是76比75大。
……
暴力求解
看到这道题我们首先想到的是暴力求解。他的原理是遍历每一个元素，然后再从当前元素往后找比它大的，找到之后记录下他俩位置的差值，然后停止内层循环，如果没找到默认为0。我们画个图来看一下
看明白了上面的分析过程，代码就容易多了，我们来看下
1public int[] dailyTemperatures(int[] T) {
2 int length = T.length;
3 int[] res = new int[length];
4 for (int i = 0; i < length; i++) {
5 for (int j = i + 1; j < length; j++) {
6 if (T[j] > T[i]) {
7 res[i] = j - i;
8 break;
9 }
10 }
11 }
12 return res;
13}使用栈解决
暴力求解，效率并不高，我们还可以使用栈来解决，栈存储的是元素的下标，不是元素的值。他的原理就是我们遍历到每个元素的时候用它和栈顶（栈不为空，如果为空直接入栈）元素比较，如果比栈顶元素小就把它对应的下标压栈，如果比栈顶元素大，说明栈顶元素遇到了右边比它大的，然后栈顶元素出栈，在计算下标的差值……重复这样计算。我们就还用上面的数据[73, 74, 75, 71, 69, 72, 76, 73]画个图来看下
搞懂了上面的分析过程我们再来看代码
1public int[] dailyTemperatures(int[] T) {
2 Stack<Integer> stack = new Stack<>();
3 int[] ret = new int[T.length];
4 for (int i = 0; i < T.length; i++) {
5 while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
6 int idx = stack.pop();
7 ret[idx] = i - idx;
8 }
9 stack.push(i);
10 }
11 return ret;
12}我们还可以用数组替换栈
1public int[] dailyTemperatures(int[] T) {
2 int[] stack = new int[T.length];
3 int top = -1;
4 int[] res = new int[T.length];
5 for (int i = 0; i < T.length; i++) {
6 while (top >= 0 && T[i] > T[stack[top]]) {
7 int idx = stack[top--];
8 res[idx] = i - idx;
9 }
10 stack[++top] = i;
11 }
12 return res;
13}参照第379题
这题和第379题有非常相似的地方，如果看过379，柱状图中最大的矩形（难），这题就非常容易了，代码也非常相似，这个栈中元素所对应值的顺序从栈底到栈顶是递减的，和379题正好相反，我们来看下代码
1public int[] dailyTemperatures(int[] T) {
2 int length = T.length;
3 Stack<Integer> stack = new Stack<>();
4 int[] res = new int[length];
5 for (int i = 0; i < length; i++) {
6 int h = T[i];
7 if (stack.isEmpty() || h <= T[stack.peek()]) {
8 stack.push(i);
9 } else {
10 int top = stack.pop();
11 res[top] = i - top;
12 i--;
13 }
14 }
15 return res;
16}剪枝
最后一种解法效率也是非常高的，代码中有注释，就不在过多解释，有兴趣的可以看下
1public int[] dailyTemperatures(int[] T) {
2 int[] res = new int[T.length];
3 //从后面开始查找
4 for (int i = res.length - 1; i >= 0; i--) {
5 int j = i + 1;
6 while (j < res.length) {
7 if (T[j] > T[i]) {
8 //如果找到就停止while循环
9 res[i] = j - i;
10 break;
11 } else if (res[j] == 0) {
12 //如果没找到，并且res[j]==0。说明第j个元素后面没有
13 //比第j个元素大的值，因为这一步是第i个元素大于第j个元素的值，
14 //那么很明显这后面就更没有大于第i个元素的值。直接终止while循环。
15 break;
16 } else {
17 //如果没找到，并且res[j]！=0说明第j个元素后面有比第j个元素大的值，
18 //然后我们让j往后挪res[j]个单位，找到那个值，再和第i个元素比较
19 j += res[j];
20 }
21 }
22 }
23 return res;
24}
长按上图，识别图中二维码之后即可关注。
如果喜欢这篇文章就点个"在看"吧