终是圣明天子事
景阳宫井又何人
C++，算是动态规划23333，也是看了评论区大神的思路。
其实很容易想到一个O(N\^2)的方法，就是从后往前遍历，对于每个T[i]，再往后找到第一个大于T[i]的数，设其为T[j]，显然找T[j]的过程复杂度也是O(N)，所以总的复杂度就是O(N\^2)了。
热评解法就是利用了一个很重要的信息，来优化找T[j]的过程。
原来我们找找T[j]，是一个一个往后遍历，即步长固定为1，但实际上是不需要的。我们用数组ans来返回答案，ans[j]记录的就是从i到第一个比T[j]大的数的距离，也就是步长为ans[j]。从i + 1开始：
- 若
T[i] < T[i+1]，那么ans[i]=1； - 若
T[i] >= T[i+1]，则往后找第一个大于T[i]的元素，步长就是ans[i]- 找到第一个大于
T[i]的元素 - 找到某个
ans[j] == 0的元素，因为等于0说明以后再也不会有元素大于T[i]了。
- 找到第一个大于
重点就是对于这个步长的理解，步长从原来的1换成了ans[j]。
class Solution {
public:
vector<int> dailyTemperatures(vector<int> &T) {
int len = T.size();
vector<int> ans(len, 0);
for (int i = len - 2; i >= 0; i--) {
for (int j = i + 1; j < len; j += ans[j]) {
if (T[i] < T[j]) {
ans[i] = j - i;
break;
} else if (ans[j] == 0) {
ans[i] = 0;
break;
}
}
}
return ans;
}
};
