LeetCode-739 每日温度

📝题目

根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

📝思路

准备两个栈保存还未得到匹配的温度和下标，遍历 temperatures 。如果该日温度超过栈顶的温度，则把栈中所有小于该日温度的数据都弹出（按照这个算法，栈中的数据必然是从大到小（底->顶）排列的）；如果该日温度低于栈顶温度，必然低于栈中所有温度，则 push 入栈中。注意栈空时的处理。

📝题解

vector<int> dailyTemperatures(vector<int>& T) {
    int len = T.size();
    vector<int> result;
    result.resize(len);
    
    stack<int> key;
    stack<int> value;
    
    for (int i = 0; i < len; ++i){
        while (!value.empty() && T[i] > value.top()){
            int t_key = key.top();
            result[t_key] = i-t_key;
            value.pop();
            key.pop();
        }       
        key.push(i);
        value.push(T[i]);
    }
    
    while (!key.empty()){
        int temp = key.top();
        key.pop();
        result[temp] = 0;
    }      
    return result;
}