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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/stack/daily-temperatures.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.