Given a list of daily temperatures T, return a list such 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 of temperatures T = [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]
题意是计算 当前温度与后面温度比当前温度要高的最近一天的距离，如第一天73度小于第二天的74度，距离就是1；第三天75度，比75高的最近的就是76，那么距离就是7-3=4
思路：可以用一个栈，该栈需要递减，栈内元素可以是温度的索引；第一天入栈，如果后一天的温度比其高则出栈，计算二者距离（后一天索引减去前一天），并把后一天入栈；如果后一天小于前一天则继续入栈。（注意：后一天并不一定指准确的第二天）（说清楚有点啰嗦，还是看代码吧）
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
vector<int> ans(T.size(),0);
stack<int> loc_stack;
for(int idx=0; idx<T.size();idx++){
while(!loc_stack.empty() && T[idx]>=T[loc_stack.top()]){
int top = loc_stack.top();
ans[top] = idx-top;
loc_stack.pop();
}
loc_stack.push(idx);
}
return ans;
}
};
int main(int argc, char const *argv[])
{
Solution solu;
vector<int> T = {73, 74, 75, 71, 69, 72, 76, 73};
vector<int> ans = solu.dailyTemperatures(T);
for(auto item:ans)
cout<<item<<" ";
return 0;
}
