这道题求下一个更大的数在哪里，如果这个数后面没有更大的数，返回 0。
可以用带优化的Brute force过，代码如下：
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
const int n = T.size();
vector<int> res (n, 0);
function<int(int, int)> findDay = [&] (int i, int j) -> int {
if (j >= n) return 0;
if (T[j] > T[i]) return j - i;
if (res[j] == 0) return 0;
return findDay(i, j + res[j]);
};
for (int i = n - 2; i >= 0; --i)
res[i] = findDay(i, i + 1);
return res;
}
};
最后一个数不存在后面，所以一定是 0，我们从倒数第二个数开始循环。首先比较数 $i$ 后面紧跟的数 $j$，如果 $j$ 比 $i$ 大，就返回 $i - j$，否则，比 $i$ 大的数一定比 $j$ 大，所以我们去寻找比 $j$ 大的数，比 $j$ 大的数已经计算了，因此可以跳过几个数或者直接剪枝，加快计算。这种方式虽然是暴力破解，可是实际跑起来不比下面介绍的 stack 方法慢太多。
这道题的考点是单调栈 （monotonic stack）,算法的核心就是维持栈单调。对于这道题来说，就是维持栈单调递减。可以从前到后遍历数组，如果栈空或者栈中元素都比当前元素大，就入栈。否则，弹出比当前元素小的数，因为他们的“下一个更大的数”已经找到了：在结果中加入距离。
class Solution {
// monotonic Stack
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
const int n = temperatures.size();
vector<int> res(n, 0);
stack<int> s;
for (int i = 0; i < n; ++i) {
while (!s.empty() && temperatures[s.top()] < temperatures[i]) {
const int j = s.top(); s.pop();
res[j] = i - j;
}
s.push(i);
}
return res;
}
};
这道题还编了一个温度变化的情境，另一道 496. Next Greater Element I 就直白多了，直接问下一个更大的元素。两者应用的算法相同。