739. Daily Temperatures

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;
}