739. Daily Temperatures

Given a list of daily temperatures, produce a list 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 temperatures = 
[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].

暴力解法(复杂度为O(n^2),编译器报超时了):

vector<int> dailyTemperatures(vector<int>& temperatures) {
    int i, j;
    int n = temperatures.size();
    vector<int> res(n);
    for (i = 0; i < n-1; i++) {  //从0到n-2
        for (j = i+1; j < n; j++) {  //j从i之后找
            if (temperatures[j] > temperatures[i]) {  //找到一个就跳出
                res[i] = j-i;
                break;
            }
        }
        if (j == n) res[i] = 0; //若找不到
    }
    res[i] = 0; //最后一位必为0
    return res;
}

别人的思路(用栈,时间O(n)(近似),空间O(n)):
上面的暴力思路是用i遍历数组,然后对每个i向后找.
现在思路是用i遍历数组,然后对每个i向前(在栈里)找.已经找到的元素直接出栈(或许这就是O(n)?),挺奇妙的.

vector<int> dailyTemperatures(vector<int>& temperatures) {
    stack<int> s;  //序号栈
    vector<int> res(temperatures.size()); //结果,长度与temps一样,初始元素全为0
    for (int i = 0; i < temperatures.size(); i++) {
        while (!s.empty() && temperatures[i] > temperatures[s.top()]) {  //若找到第一个比栈顶温度大的
            res[s.top()] = i - s.top();  //i与栈顶的序号之差
            s.pop();  //出栈
        }
        s.push(i); //若没找到比栈顶大的,先把i入栈,成为新栈顶
    }
    return res;
}