Question
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
Analysis
借着这道题学习了一下单调栈。比如以下测试数据：
[89,62,70,58,47,47,46,76,100,70]
本来只能想到 的笨方法，也就是不使用额外的数据结构存储，对于每个元素找它的下一个更大的元素，这样写起来很容易但是有很多冗余的比较。这里对于任何元素而言，比它小的元素都不需要比较。
从左往右
比如，从左往右看：
__ | 89
89 | 62
89 62 | 70
此时，对于 70 而言，它左侧的数据小于它，70所处的位置就是它左侧元素的解。
__ 1 __ ...
此时，让 62 出栈（更小的元素，冗余，无需比较），让 70 入栈：
89 70 | 58
89 70 58 | 47
89 70 58 47 | 47
89 70 58 47 47 | 46
89 70 58 47 47 46 | 76
对于 76，左侧 5 个数都比它小，因此左侧 5 个数对应的解是 76。
__ 1 5 4 3 2 1 ...
继续：
89 76 | 100
100 同理：
8 1 5 4 3 2 1 1 ...
最后一个是 70：
100 70
此时数组遍历到最后，没有更多元素了，因此对于这两个元素没有符合的解，用 0 代替。
8 1 5 4 3 2 1 1 0 0
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int len = temperatures.size();
vector<int> res(len);
std::stack<int> s;
s.push(0);
for (int i = 1; i < len; i++) {
while (!s.empty() && temperatures[s.top()] < temperatures[i]) {
res[s.top()] = i - s.top();
s.pop();
}
s.push(i);
}
return res;
}
};
从右往左
反过来，也是类似的看法，但这时候不是一边出栈一边记录，而是完全出栈后才记录结果。
while (!s.empty() && temperatures[s.top()] <= temperatures[i]) {
s.pop();
}
70 | 100
100 | 76
对于 70 或者 100 而言，它只关注它左侧第一个小于等于它的数，因此，当栈中没有符合要求的数时，它们的解就是 0，而且栈中不会存它们之外的值。
此时 100 是 76 的解，因此 76 入栈，100 出栈，把 76 的位置填上对应的解。
76 | 46 <- 同理
46 | 47
46 47 | 47 <- 47 出栈
46 47 | 58
46 47 58 | 70
46 47 58 70 | 62 <- 70 出栈
46 47 58 62 | 89
对于每个入栈的元素而言，它的解就是当前栈顶元素。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int len = temperatures.size();
vector<int> res(len);
std::stack<int> s;
for (int i = len - 1; i >= 0; i--) {
while (!s.empty() && temperatures[s.top()] <= temperatures[i]) {
s.pop();
}
res[i] = s.empty() ? 0 : (s.top() - i);
s.push(i);
}
return res;
}
};