題目描述
請(qǐng)根據(jù)每日 氣溫 列表，重新生成一個(gè)列表。對(duì)應(yīng)位置的輸出為：要想觀測(cè)到更高的氣溫，至少需要等待的天數(shù)。如果氣溫在這之后都不會(huì)升高，請(qǐng)?jiān)谠撐恢糜?0 來代替。
例如，給定一個(gè)列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應(yīng)該是[1, 1, 4, 2, 1, 1, 0, 0]。
這個(gè)輸出我看了半分鐘才看明白，可能需要解釋一下：
從第0天開始，第1天的溫度比它高，意思就是第0天需要等待1天就能觀測(cè)到更高的氣溫，所以下標(biāo)0填1。
第2天溫度比第1天高，則第1天同樣僅需等待1天就能觀測(cè)到更高到氣溫，所以下標(biāo)1也填1。
第2天的溫度是75，往后第3，4，5天的溫度都低于第2天，到了第6天溫度才高于第2天，所以第2天需要等待4天才能觀測(cè)到更高氣溫，下標(biāo)2填4。
第6天的溫度是76，往后的每一天的溫度都比它低，也就是等不到能觀測(cè)到比第6天更高氣溫的那天，按題目要求填0.
第7天是最后一天，沒有參照物比較，也填0.
最后正確的輸出就應(yīng)該是：[1, 1, 4, 2, 1, 1, 0, 0]
提示：氣溫 列表長度的范圍是 [1, 30000]。每個(gè)氣溫的值的均為華氏度，都是在 [30, 100] 范圍內(nèi)的整數(shù)。
方法一：暴力解法
思路：
這個(gè)題目簡單理解就是對(duì)于位置i，找到位置j，位置j是滿足：
j > itemperatures[j] > temperatures[i]
兩個(gè)條件的最小下標(biāo)。
所以對(duì)于每個(gè)位置，都從該位置+1的地方往后遍歷，找到第一個(gè)大于它的值，計(jì)算兩個(gè)下標(biāo)差值即可。
代碼：
var dailyTemperatures = function(temperatures) {
let len = temperatures.length
if(len <= 0) return []
let res = []
// 最后一個(gè)元素后面一定沒有比它大的值
res[len-1] = 0
for(let i = len-2; i >= 0; i--) {
let target = temperatures[i]
for(let j = i+1; j < len; j++) {
let current = temperatures[j]
if(current > target) {
res[i] = j-i
break;
}
}
// 這里的意思是該位置后面沒有出現(xiàn)過比它大的值
if(res[i] === undefined) {
res[i] = 0;
}
}
return res;
};
性能：
時(shí)間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(n)
方法二：單調(diào)棧
單調(diào)棧就是棧中的元素滿足單調(diào)遞增或遞減。
思路：
如果相鄰位置的兩個(gè)數(shù)，前一個(gè)數(shù)小于后一個(gè)數(shù)，則很明顯，前一個(gè)位置的結(jié)果就是1，即只需要等待一天。
如果前一個(gè)數(shù)大于后一個(gè)數(shù)，則前一個(gè)位置的結(jié)果不能確定，需要指針繼續(xù)向后走，直到一個(gè)比它大的數(shù)出現(xiàn)，才能知道其需要等待的天數(shù)。
也就是說，對(duì)于每個(gè)位置來說，都只需要找到往后最小的下標(biāo)，滿足其氣溫高于當(dāng)前位置。
對(duì)于暫時(shí)還未找到更高氣溫的位置，存入棧中，指針每一次向后移動(dòng)時(shí)，和棧中元素比較，如果發(fā)現(xiàn)更高，表示棧中存放的元素可以確定等待天數(shù)了，則該元素出棧。
按這個(gè)思路你會(huì)發(fā)現(xiàn)，能存入棧中的元素，滿足一個(gè)條件：棧中元素是遞減的（從棧底到棧頂），不會(huì)存在新入棧的元素比棧頂元素更大的情況，因?yàn)檫@種情況下，棧頂元素就直接出棧了（已經(jīng)找到了等待天數(shù)自然就不會(huì)呆在棧中了）
當(dāng)棧頂元素出棧后，棧頂變成了之前的第二位元素，此時(shí)，新棧頂元素和指針指向的元素大小關(guān)系如何呢？比較一下就知道了，如果新棧頂元素也能出棧，則繼續(xù)比較，直到棧空。如果不能出棧，將指針指向元素推入棧中，指針繼續(xù)向后移動(dòng)。
好了，這就是解題思路了。
來個(gè)例子理解一下。
溫度列表：temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
指針：p = 0
單調(diào)棧：stack = []
結(jié)果: res = []
p=0時(shí)，?？眨?直接入棧, stack=[0]
p=1時(shí)，棧頂值是0，temperatures[1]大于temperatures[0]，0出棧，同時(shí)res[0] = 1-0, 此時(shí)?？?，1直接入棧, stack=[1]
p=2同理，res[1] = 2-1, stack=[2]
p=3時(shí), 棧頂值是2，temperatures[3]小于temperatures[2]，3入棧, stack=[2, 3]
p=4時(shí)，棧頂值是3，temperatures[4]小于temperatures[3]，4入棧，stack=[2, 3, 4]
p=5時(shí)，此時(shí)棧中元素如下：
棧頂值是4，
temperatures[5]大于temperatures[4]，4可以出棧，同時(shí)res[4] = 5-4,此時(shí)棧中還有元素，棧頂值變成3，繼續(xù)比較。
temperatures[5]大于temperatures[3]，3可以出棧，同時(shí)res[3] = 5-3，此時(shí)棧中還有元素，棧頂值變成2，繼續(xù)比較。temperatures[5]小于temperatures[2]，5入棧，stack=[2, 5]
p=6時(shí)，棧頂值是5，temperatures[6]大于temperatures[5]，5出棧，同時(shí)res[5] = 6-5, 此時(shí)棧中還有元素，棧頂值變成2，繼續(xù)比較。
temperatures[6]大于temperatures[2]，2出棧，同時(shí)res[2] = 6-2, 此時(shí)?？?，6直接入棧。
p=7時(shí)，temperatures[7]小于temperatures[6]，7入棧，stack=[6, 7]
p=8時(shí)，越界，退出循環(huán)。
此時(shí)棧中還有兩個(gè)元素，它們的等待天數(shù)也還是未知的，不過這里稍微想一想就能發(fā)現(xiàn)，這兩個(gè)元素，都是沒有找到更高氣溫的，所以等待天數(shù)為0.
代碼：
var dailyTemperatures = function(temperatures) {
let stack = []
let res = []
for(let i = 0, len = temperatures.length; i < len; i++) {
while(stack.length && temperatures[stack[stack.length-1]] < temperatures[i]) {
let j = stack.pop()
res[j] = i-j
}
stack.push(i)
}
//最后棧內(nèi)存在的元素代表的是在該位置后沒有比它更大的值，所以都填0
while(stack.length) {
res[stack.pop()] = 0
}
return res
}
性能：
時(shí)間復(fù)雜度：O(n) （不太明白for循環(huán)中嵌套了while循環(huán)為什么還是O(n)，知道的小伙伴評(píng)論里求解答）
空間復(fù)雜度：O(n)
