# Daily Temperatures

`stack`, `monotonous stack`

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

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

## Analysis

### Brute-force

Brute-force的方法就略去不表，时间复杂度O(n^2)。

### Stack

Brute-force有很多是重复搜索，更有效率的是利用Stack，一个单调递增的stack。逆序的方式进行扫描。

举例：

`T = [73, 74, 75, 71, 69, 72, 76, 73]`

如下：

```
When i = 7, stack = [7 (73)]. ans[i] = 0.
When i = 6, stack = [6 (76)]. ans[i] = 0.
When i = 5, stack = [5 (72), 6 (76)]. ans[i] = 1.
When i = 4, stack = [4 (69), 5 (72), 6 (76)]. ans[i] = 1.
When i = 3, stack = [3 (71), 5 (72), 6 (76)]. ans[i] = 2.
When i = 2, stack = [2 (75), 6 (76)]. ans[i] = 4.
When i = 1, stack = [1 (74), 2 (75), 6 (76)]. ans[i] = 1.
When i = 0, stack = [0 (73), 1 (74), 2 (75), 6 (76)]. ans[i] = 1.
```

对于结果来说：

`ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;`

**注意：**

`T[i] >= T[stack.peek()]`时候要不断`pop()`，然后再放入当前下标i。这里要允许`"="`的条件，因为需要寻找第一个出现的位置，因此重复位置要`pop()`出来。

这一题用**Stack**很妙，十分经典。As @FrancisGee points out:

> When I saw the question in this competition, I firstly think about **Monotonous** **stack** inspired by ***Largest Rectangle in Histogram***. Because Monotonous stack can help us find first largest element in O(n) time complexity.

这种**单调栈**的思想需要多加琢磨咀嚼。

Time Complexity - O(n)

Space Complexity - O(n)

## Solution

Stack with reverse order iteration T.length - 1 to 0 - Time: O(n), Space: O(n) - (52 ms)

```java
class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] ans = new int[T.length];
        Deque<Integer> stack = new ArrayDeque<>();    

        for (int i = T.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && T[i] >= T[stack.peek()]) {
                stack.pop();
            }
            ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }
        return ans;
    }
}
```

**Stack with 0 to T.length - 1 order** iteration (17 ms, faster than 92.98%)

Using ArrayDeque() will significantly increase performance than Stack()

```java
class Solution {
    public int[] dailyTemperatures(int[] T) {
        Deque <Integer> stack = new ArrayDeque<>();
        int[] ret = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int idx = stack.pop();
                ret[idx] = i - idx;
            }
            stack.push(i);
        }
        return ret;
    }
}
```

Brute-force O(n^2) - (348 ms)

```java
class Solution {
    public int[] dailyTemperatures(int[] T) {
        int n = T.length;
        int[] ans = new int[n];
        int days = 0;
        for (int i = 0; i < n; i++) {
            days = 0;
            for (int j = i; j < n; j++) {
                if (T[j] > T[i]) {
                    ans[i] = days;
                    break;
                } else {
                    days++;
                }
            }
        }
        return ans;
    }
}
```

## Reference

<https://leetcode.com/problems/daily-temperatures/solution/>

<https://leetcode.com/problems/daily-temperatures/discuss/109832/Java-Easy-AC-Solution-with-Stack>