题目

链接：739. 每日温度
难度：Medium

题解

题解一

分析

只要确定有解且算力足够，暴力（枚举）搞定一切。对于某一天i的气温遍历搜索其之后的每天气温，不存在更大值则result[i] = 0；存在某一天j高于i，则result[i] = j - i。

时间复杂度

$n*(n-1)$

实现

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> ret(T.size());
        for(int i = 0; i < T.size() - 1; ++i) {
            int j;
            for(j = i + 1; j < T.size(); ++j) {
                if(T[j] > T[i]) {
                    ret[i] = j - i;
                    break;
                }
            }
            if(j == T.size()) {
                ret[i] = 0;
            }
        }
        return ret;
    }
};

题解二

分析

维护一个递减栈：当某一天的气温低于栈顶气温时，把它入栈；反之当某一天气温大于栈顶气温时（假设当天为j，栈顶为i），result[i] = j - i，把i出栈并在栈为空之前循环判断T[j]和T[top]，直到栈为空或者T[j]不大于栈顶元素。遍历完整个T之后，result中其余未被修改过的元素都为0。

时间复杂度

最好情况：T为递减数组，遍历完整个T即可结束，$n$
最坏情况：T[0]~T[n-2]递减，但T[n-1] > T[0]，$n + (n - 1)$

实现

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

题解三

分析

无论什么样的数据，最后一天的result一定是0，即result[n-1] = 0，而每一天的结果只与这一天之后的每天有关，所以考虑从尾到头推算结果。

• result[n-1] = 0

• 对于非最后一天的某天i，与下一天j = i + 1比较：

  • 如果T[i] < T[j]，那么result[i] = j - i = 1
  • 否则，寻找j之后比j大的数，即j = j + result[j]，比较，如果T[i] < T[j], 那么result[i] = j - i
  • 否则重复上一步直到result[j] = 0。此时，j之后已经不存在比j大的数了，而T[j]又不大于T[i]，所以i之后不存在比i大的数，即result[i] = 0

时间复杂度

时间复杂度和题解二基本一致，不过最好情况变为：T为递增数组。
但是，这个方法只用到了T[]和result[]，相比题解二少了一个递减栈的内存消耗。

实现

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int size = T.size();
        vector<int> ret(size);
        ret[size-1] = 0;
        for(int i = size - 2; i >= 0; --i) {
            for(int j = i + 1; j < size; j += ret[j]) {
                if(T[i] < T[j]) {
                    ret[i] = j - i;
                    break;
                } else {
                    if(ret[j] == 0) {
                        ret[i] = 0;
                        break;
                    }
                }
            }
        }
        return ret;
    }
};