### 主要收获

|
|         |
| |   |   |     |
| | | | | | | | |
-----------------
4 2 1 2 1 3 1 1 2
|-----| |
^    | 这个3 决定了左边4个比他小的数字的最近更大元素。
|    |
+----+


### 题目

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

### 从后往前遍历，$O(n)$

#### 代码

class Solution {
private static int[] memo = new int[101];

public int[] dailyTemperatures(int[] temperatures) {
Arrays.fill(memo,0);
int[] res = new int[temperatures.length];
for (int i = temperatures.length-1; i >= 0; i--) {
int temperature = temperatures[i];
int wait = Integer.MAX_VALUE;
for (int j = temperature + 1; j < 101; j++) {
int future = memo[j];
if (future > i) {
wait = Math.min(wait,future - i);
}
}
res[i] = (wait == Integer.MAX_VALUE)? 0 : wait;
memo[temperature] = i;
}
return res;
}
}


### 用Stack是这一类题目的标准解法，$O(n)$

|
|         |
| |   |   |     |
| | | | | | | | |
-----------------
4 2 1 2 1 3 1 1 2
|-----| |
^    | 这个3 决定了左边4个比他小的数字的最近更大元素。
|    |
+----+


76
76, 74
76,74,71


76,75


#### 代码

class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] stack = new int[temperatures.length];
int[] res = new int[temperatures.length];
int top = -1;
for (int i = 0; i < temperatures.length; i++) {
while (top > -1 && temperatures[i] > temperatures[stack[top]]) {
int index = stack[top--];
res[index] = i - index;
}
stack[++top] = i;
}
return res;
}
}