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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> temperatures = [73,74,75,71,69,72,76,73]
<strong>Output:</strong> [1,1,4,2,1,1,0,0]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> temperatures = [30,40,50,60]
<strong>Output:</strong> [1,1,1,0]
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> temperatures = [30,60,90]
<strong>Output:</strong> [1,1,0]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;=&nbsp;temperatures.length &lt;= 10<sup>5</sup></code></li>
	<li><code>30 &lt;=&nbsp;temperatures[i] &lt;= 100</code></li>
</ul>

'''
\U0001f50e EXPLORE
What are some other insightful & revealing test cases?
    
       i
[4, 2, 5, 4, 3, 2, 1]

[2, 1, 0, 0, 0, 0,0]

input:
[20, 30, 40]
output:
[1, 1, 0]

\U0001f9e0 BRAINSTORM
What approaches could work?
Algorithm 1: iterate through and have a runner index for finding the days
Time: O(n^2)
Space: O(n)


input:

      
[20, 30, 40]
\U0001f4c6 PLAN
Outline of algorithm 1:
length = len(temperatures)
ans = [0 for x in range(length)]
for temp in range(length):
    runner = temp + 1
    current_temp = temperatrues[temp]
    while runner < length and current_temp < temperatures[runner]:
        runner+=1
    if runner == length:
        ans[temp] = 0
    else:
        ans[temp] = runner - temp
return ans

 

\U0001f6e0️ IMPLEMENT
Write your algorithm.
 

\U0001f9ea VERIFY
Run tests. Methodically debug & analyze issues.


length = 8
ans = [0,0,0,0,0,0,0,0] 
                   i
temperatures = [73,74,75,71,69,72,76,73]

stack = [0, ]
i = 1



'''

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        length = len(temperatures)
        ans = [0 for x in range(length)]
        stack = []

        for i in range(length):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                index = stack.pop()
                ans[index] = i - index
            stack.append(i)
        return ans

30200