Problem#
給你一個整數陣列 $T[i]$ 要你回答一個整數陣列 $ans$ ，其中 $ans[i]$ 代表對於第 $i$ 天的溫度 $T[i]$ 會存在一個溫度 $T[j]$ 且 $j = i + ans[i]$ 使得 $T[i] < T[j]$
想法#
naive: 對每個數字往後去找第一個比它大的 $O(n^2)$ TLE
維護一個 monotonic stack 代表等待比他大的溫度的列表(可以用 pair<int,int> 一起存 (idx, temp))，接著遍歷 temp[i] 如果大於 stack 頂端的溫度，就代表裏頭的溫度遇到比它大的，所以就計算 ans[i] 接著 pop stack；接著把目前的 idx 和 temp[idx] 堆進 stack 中 (找比它大的溫度距離它多少)
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(n)$
AC Code#
賞析#
https://www.cnblogs.com/grandyang/p/8097513.html
https://oi-wiki.org/ds/monotonous-stack/
https://leetcode.com/problems/daily-temperatures/solutions/1516538/daily-temperatures/?orderBy=hot
心得#
這種我一開始都沒想到要怎麼做= = ，要多寫一點這種題目