739. Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

• 1 <= temperatures.length <= 105

• 30 <= temperatures[i] <= 100

My Solutions:

对每一个index上的数字，求需要过几天才能有一个比TA大的数字出现。

维护一个stack，stack里储存index。从array的后面往前遍历，如果array里当前的数字比stack peek的要大，则把stack里的元素pop出来。此时如果stack不为空，说明当前天数之后有比此时更热的天，需要计算index之间相差多少。然后把当前index push进去。这样保证了stack里存的index代表的是最大的温度在最下面，存的index代表的温度一定是递增的。

比如对于example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
        index       = [0,  1, 2, 3, 4, 5, 6, 7]
Output:               [1,  1, 4, 2, 1, 1, 0, 0]

• index=7, stack=[7]

• index=6, stack pop出7，stack=[6]

• index=5, stack=[6,5]

• index=4, stack=[6,5,4]

• index=3, stack变成[6,5],再变成[6,5,3]

• index=2, stack变成[6], 再变成[6,2]

• index=1, stack=[6,2,1]

• index=0, stack=[6,2,1,0]

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // 维护一个绝对递增的stack
        Stack<Integer> stack = new Stack<>(); // store index
        int len = temperatures.length;
        int[] res = new int[len];
        for (int i = len - 1; i >= 0; i--) {
            while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) res[i] = stack.peek() - i;
            stack.push(i);
        }

        return res;
    }
}

变种：如果这道题要算每个temperature是前面多少天内的最热气温？

e.g. [10,30,60,20,10,40,80,90] --> [1,2,3,1,1,‍‌‌‌‍‌‍‍‍‍‌‍‍‌‍‌‌3,7,8]

对每个数字往前数，直到发现一个比TA大的天数。Time: O(n^2)

        for (int i = len - 1; i >= 0; i--) {
            int count = 1;
            for (int j = i; j > 0; j--) {
                if (temperatures[i] - temperatures[j - 1] >= 0) count++;
                else break;
            }
            res[i] = count;
        }
        return res;