LeetCode 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].

解析：给定一组数值，表示每天的温度，计算数组中每个数值经过几天后温度更高。即计算数组中每个数值num，找到num后面第一个比num大的数值。首先考虑的是暴力法，遍历每个位置i的数值，然后对于每个i处的数字，遍历从i到后面的每个数字，判断是否比i处的数字大。但是这样时间复杂度是\(O(N^2)\)。考虑时间复杂度更低的方法，采用栈来处理，维护一个递减栈，如果栈为空或者当前元素比栈顶元素小或者等于，则入栈；否则出栈，遍历每一个栈顶元素，如果当前当前元素大于栈顶元素，则栈顶出栈，计算间隔存放到res数组中。具体代码如下：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int len = T.size();
        stack<int> st;
        vector<int> res(len, 0);
        for(int i = 0; i < len; i++)
        {
            while(!st.empty() && T[st.top()] < T[i])
            {
                int index = st.top();
                st.pop();
                res[index] = i-index;
            }
            st.push(i);
        }
        return res;
    }
};