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

解题步骤

这又是一道可以用Stack来解决的问题。

1. 建立降序栈stk,存temperatures数组对应的 index
2. 建立返回数组rets并且初始化为0
3. 遍历temperatures数组：
   • 每一个元素temp和stk的栈顶元素对应值比较，如果temp较大，说明遇到了 warmer temperature，所以在rets中更新栈顶元素对应的值，并且 pop 栈顶元素
   • 重复上述过程，直到stk为空或者temp比栈顶值小，将当前index 进栈

示例代码(CPP)

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        // 注意需要初始化为0
        vector<int> rets(n, 0);
        stack<int> stk;
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
                rets[stk.top()] = i - stk.top();
                stk.pop();
            }
            // 注意push的是index，不是值
            stk.push(i);
        }
        return rets;
    }
};

示例代码(PYTHON)

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        # 使用List代替stack
        stack = list()
        res = [0 for  i in range(len(temperatures))]
        for i in range(len(temperatures)):
            while(len(stack) > 0 and temperatures[i] > temperatures[stack[-1]]):
                res[stack[-1]] = i - stack[-1];
                stack.pop()
            # append等效为stack中的push
            stack.append(i)
        return res

复杂度分析

因为每个字符push和pop都是最多一次，所以：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

总结归纳：

运用Stack的题目很多，这类问题的做法是遍历输入数组，当前元素与栈顶元素比较，如果当前元素更优（不同题目条件不同，比如本题对应当前元素较大）则pop栈顶元素，直到栈顶元素更优为止，而后插入当前元素。

类似的题目还有：
[LeetCode 316] Remove Duplicate Letters 移除重复字母

最近会总结更多这类题目更新在Stack Tag中，尽请期待，吃香蕉去了：）