"""
main idea is (monotonous stack) to loop through each element in the T, record with old temprature with stack(from old to most recent).
compare current temperate with most recent temperature, if current is higher than most recent, get the difference with current and most recent, store into result at position most recent.
Meanwhile, keep checking if current temperature still higher than historical temperatures that uncalculated yet (in the stack), keep processing them until reach to the point historical temperature is higher than current, then make current temperature into stack.
"""
# time O(N) space O(S) S: size of stack ~ worst N
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
res = [0] * len(T)
st = []
for i,v in enumerate(T):
while st and v > st[-1][0]:
_,idx = st.pop()
res[idx] = i-idx
#print(f'idx is {idx}, i is {i}, res[idx] is {res[idx]}')
st.append((v,i))
return res