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

b'
\n\n

#### Approach #1: Next Array [Accepted]

\n

Intuition

\n

The problem statement asks us to find the next occurrence of a warmer temperature. Because temperatures can only be in `[30, 100]`, if the temperature right now is say, `T[i] = 50`, we only need to check for the next occurrence of `51`, `52`, ..., `100` and take the one that occurs soonest.

\n

Algorithm

\n

Let\'s process each `i` in reverse (decreasing order). At each `T[i]`, to know when the next occurrence of say, temperature `100` is, we should just remember the last one we\'ve seen, `next[100]`.

\n

Then, the first occurrence of a warmer value occurs at `warmer_index`, the minimum of `next[T[i]+1], next[T[i]+2], ..., next[100]`.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of `T` and is the number of allowed values for `T[i]`. Since , we can consider this complexity .

\n
• \n
• \n

Space Complexity: , the size of the answer and the next array.

\n
• \n
\n
\n

#### Approach #2: Stack [Accepted]

\n

Intuition

\n

Consider trying to find the next warmer occurrence at `T[i]`. What information (about `T[j]` for `j > i`) must we remember?

\n

Say we are trying to find `T[0]`. If we remembered `T[10] = 50`, knowing `T[20] = 50` wouldn\'t help us, as any `T[i]` that has its next warmer ocurrence at `T[20]` would have it at `T[10]` instead. However, `T[20] = 100` would help us, since if `T[0]` were `80`, then `T[20]` might be its next warmest occurrence, while `T[10]` couldn\'t.

\n

Thus, we should remember a list of indices representing a strictly increasing list of temperatures. For example, `[10, 20, 30]` corresponding to temperatures `[50, 80, 100]`. When we get a new temperature like `T[i] = 90`, we will have `[5, 30]` as our list of indices (corresponding to temperatures `[90, 100]`). The most basic structure that will satisfy our requirements is a stack, where the top of the stack is the first value in the list, and so on.

\n

Algorithm

\n

As in Approach #1, process indices `i` in descending order. We\'ll keep a `stack` of indices such that `T[stack[-1]] < T[stack[-2]] < ...`, where `stack[-1]` is the top of the stack, `stack[-2]` is second from the top, and so on; and where `stack[-1] > stack[-2] > ...`; and we will maintain this invariant as we process each temperature.

\n

After, it is easy to know the next occurrence of a warmer temperature: it\'s simply the top index in the stack.

\n

Here is a worked example of the contents of the `stack` as we work through `T = [73, 74, 75, 71, 69, 72, 76, 73]` in reverse order, at the end of the loop (after we add `T[i]`). For clarity, `stack` only contains indices `i`, but we will write the value of `T[i]` beside it in brackets, such as `0 (73)`.

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

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of `T` and is the number of allowed values for `T[i]`. Each index gets pushed and popped at most once from the stack.

\n
• \n
• \n

Space Complexity: . The size of the stack is bounded as it represents strictly increasing temperatures.

\n
• \n
\n
\n

Analysis written by: @awice.

\n
'