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 0instead.

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

思路一：写一个子函数用来算每一天对应的答案，然后依次遍历T数组，求得结果，然而这种暴力搜索超时

代码一：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> res;
        for (int i = 0; i < T.size(); ++i) {
            res.push_back(findnum(T, i));
        }
        return res;
    }
    
    int findnum(vector<int> &T, int start) {
        int ans = 1;
        int i;
        for (i = start+1; i < T.size(); ++i) {
            if (T[start] < T[i]) break;
            ++ans;
        }
        return (i == T.size()) ? 0 : ans;
    }
};

思路二：

这道题给了我们一个数组，让我们找下一个比当前数字大的数字的距离，我们研究一下题目中给的例子，发现数组是无序的，所以没法用二分法快速定位下一个大的数字，那么最先考虑的方法就是暴力搜索了，写起来没有什么难度，但是OJ并不答应。实际上这道题应该使用递减栈Descending Stack来做，栈里只有递减元素，思路是这样的，我们遍历数组，如果栈不空，且当前数字大于栈顶元素，那么如果直接入栈的话就不是递减栈了，所以我们取出栈顶元素，那么由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，那么我们直接求出下标差就是二者的距离了，然后继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来了。

代码二：

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

以后会开始使用python刷题，因此这里附上思路二对应的python3代码。

代码三（python3代码）：

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        ans = [0] * len(T)
        stack = []
        for i in range(len(T)):
            while (stack and T[i] > T[stack[-1]]):
                t = stack[-1]
                stack.pop()
                ans[t] = i - t
            stack.append(i)
        return ans