0739. Daily Temperatures.md

739. Daily Temperatures, medium

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]

// 188ms, 100%
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> res(T.size(), 0);
        
        for (int i = T.size()-2; i >= 0; i--) {
            int j = i + 1;
            while (j < T.size()) {
                if (T[i] < T[j]) {
                    res[i] = j - i;
                    break;
                }
                if (res[j] == 0) break;
                
                if (T[i] == T[j]) {
                    res[i] = res[j] + j - i;
                    break;
                }
                
                j = j + res[j];
            }
        }
        return res;
    }
};