[LeetCode] 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].

這道題給了我們一個數組，讓我們找下一個比目前數字大的數字的距離，我們研究一下題目中給的例子，發現數組是無序的，是以沒法用二分法快速定位下一個大的數字，那麼最先考慮的方法就是暴力搜尋了，寫起來沒有什麼難度，但是OJ并不答應。實際上這道題應該使用遞減棧Descending Stack來做，棧裡隻有遞減元素，思路是這樣的，我們周遊數組，如果棧不空，且目前數字大于棧頂元素，那麼如果直接入棧的話就不是遞減棧了，是以我們取出棧頂元素，那麼由于目前數字大于棧頂元素的數字，而且一定是第一個大于棧頂元素的數，那麼我們直接求出下标差就是二者的距離了，然後繼續看新的棧頂元素，直到目前數字小于等于棧頂元素停止，然後将數字入棧，這樣就可以一直保持遞減棧，且每個數字和第一個大于它的數的距離也可以算出來了，參見代碼如下： 

參考資料：

<a href="https://discuss.leetcode.com/topic/112830/java-easy-ac-solution-with-stack">https://discuss.leetcode.com/topic/112830/java-easy-ac-solution-with-stack</a>

，如需轉載請自行聯系原部落客。