> [!META]- Inline Metadata
> [tags:: #career #leetcode/stacks #concepts/programming/stacks]
> [project group:: Neetcode 150]
> [difficulty:: medium]
> [status:: done]
> [link:: https://leetcode.com/problems/daily-temperatures/]
> [up:: [[Leetcode MOC]]]
## Problem
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:**
**Input:** temperatures = [73,74,75,71,69,72,76,73]
**Output:** [1,1,4,2,1,1,0,0]
**Example 2:**
**Input:** temperatures = [30,40,50,60]
**Output:** [1,1,1,0]
**Example 3:**
**Input:** temperatures = [30,60,90]
**Output:** [1,1,0]
**Constraints:**
- `1 <= temperatures.length <= 105`
- `30 <= temperatures[i] <= 100`
## Solution
### Mine
#### Python
```python
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
result = [0] * len(temperatures)
stack = []
for idx, val in enumerate(temperatures):
while stack and val > stack[-1][1]:
result[stack[-1][0]] = idx - stack[-1][0]
stack.pop()
if not stack or val <= stack[-1][1]:
stack.append((idx, val))
return result
```
#### Rust
### LC's
## Things I Learned
## Scratchpad
Brute force is $O(n^2)$
However, as we iterate, we can use a stack for $O(n)$. As you iterate through initial list, append "current" temp to stack, then if next one is greater you're done and can pop it.
But if next temp is lower? Add it to stack as well.
Stack will be in [[Monotonic Descreasing Order]].
Now, once you get to a number that's greater than the top of the stack, you pop it, and check the next one. Add difference between indices to answer list. Once equal or lesser to top of stack, append it.
![[Pasted image 20221024122948.png]]
In our stack, we should add a tuple of idx and temperature because we need both.