# 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:**

<pre><code><strong>Input: temperatures = [73,74,75,71,69,72,76,73]
</strong><strong>Output: [1,1,4,2,1,1,0,0]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: temperatures = [30,40,50,60]
</strong><strong>Output: [1,1,1,0]
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: temperatures = [30,60,90]
</strong><strong>Output: [1,1,0]
</strong></code></pre>

**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:

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

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

```java
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)

```java
        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;
```