摘要：提示氣溫列表長(zhǎng)度的范圍是。第二次遍歷棧頂對(duì)應(yīng)索引的溫度索引出棧此時(shí)棧為空，。索引入棧，第三次遍歷棧頂對(duì)應(yīng)索引的溫度滿足要求當(dāng)前索引入棧。每個(gè)氣溫的值的均為華氏度，都是在范圍內(nèi)的整數(shù)。

根據(jù)每日 氣溫 列表，請(qǐng)重新生成一個(gè)列表，對(duì)應(yīng)位置的輸入是你需要再等待多久溫度才會(huì)升高超過該日的天數(shù)。如果之后都不會(huì)升高，請(qǐng)?jiān)谠撐恢糜?0 來(lái)代替。

例如，給定一個(gè)列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]。

Given a list of daily temperatures T, return a list such 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 of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

提示：氣溫 列表長(zhǎng)度的范圍是 [1, 30000]。每個(gè)氣溫的值的均為華氏度，都是在 [30, 100] 范圍內(nèi)的整數(shù)。

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

最容易想到和理解的就是暴力窮舉，兩個(gè)指針，一個(gè)指針指向當(dāng)前溫度，第二指針向后遍歷找到最近一個(gè)比當(dāng)前溫度高的溫度，記錄兩個(gè)指針的索引差即可?？梢哉f效率非常低了。

另一種方法是借助棧倒序遍歷原數(shù)組，存入較高的溫度的索引，也很容易理解，時(shí)間復(fù)雜度為 O(n)。其實(shí)現(xiàn)邏輯為：

原數(shù)組：[73, 74, 75, 71, 69, 72, 76, 73]，指針 i 從末尾向前遍歷，返回?cái)?shù)組res=[0，0，0，0，0，0，0]

第一次遍歷: i = 7, T[i] = 73, stack = []
        棧為空，res[7] = 0 ,73所在索引7入棧。stack = [7]

第二次遍歷: i = 6, T[i] = 76, stack = [7]
        棧頂對(duì)應(yīng)索引7的溫度T[7]=76,76>73,索引7出棧,此時(shí)棧為空，res[6] = 0。索引6入棧，stack = [6]

第三次遍歷: i = 5, T[i] = 72, stack = [6]
        棧頂對(duì)應(yīng)索引6的溫度T[6]=76,72<76,滿足要求,當(dāng)前索引5入棧。res[5] = 棧頂索引6 - 當(dāng)前索引5 = 1, stack = [6,5]

第四次遍歷: i = 4, T[i] = 69, stack = [6,5]
        棧頂對(duì)應(yīng)索引5的溫度T[5]=72,69<72,滿足要求,當(dāng)前索引4入棧。res[4] = 棧頂索引5-當(dāng)前索引4=1, stack = [6,5,4]

第五次遍歷: i = 3, T[i] = 71, stack = [6,5,4]
        棧頂對(duì)應(yīng)索引的溫度T[4]=69,71>69,棧頂元素出棧。stack = [6,5]
        棧頂對(duì)應(yīng)索引的溫度T[5]=72,滿足要求,當(dāng)前索引3入棧。res[3] = 棧頂索引5-當(dāng)前索引3=2, stack = [6,5,3]

第六次遍歷: i = 2, T[i] = 75, stack = [6,5,3]
        棧頂對(duì)應(yīng)索引的溫度T[3]=71,75>71,棧頂元素出棧。stack = [6,5]
        棧頂對(duì)應(yīng)索引的溫度T[5]=72,75>72,棧頂元素出棧。stack = [6]
        棧頂對(duì)應(yīng)索引的溫度T[6]=76,75<76,滿足要求，當(dāng)前索引2入棧。res[2] = 棧頂索引6-當(dāng)前索引2=4, stack = [6,2]

第七次遍歷: i = 1, T[i] = 74, stack = [6,2]
        棧頂對(duì)應(yīng)的溫度T[2]=75,滿足要求,當(dāng)前索引1入棧。res[1] = 2-1=1, stack = [6,2,1]

第八次遍歷: i = 0, T[i] = 73, stack = [6,2,1]
        棧頂對(duì)應(yīng)的溫度T[1]=74,滿足要求,當(dāng)前索引0入棧。res[0] = 1-0=1, stack = [6,2,1,0]

遍歷結(jié)束: res = [1,1,4,2,1,1,0,0]

這種方法下，棧存入索引對(duì)應(yīng)的溫度值始終按升序排列，當(dāng)棧為空時(shí)，證明當(dāng)前溫度為 從該溫度向后的所有溫度里 最大的。

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int len=T.length;
        int[] res = new int[len];
        Stack stack = new Stack<>();//初始化棧
        for (int i = len - 1; i >= 0; i--) {
            while (!stack.isEmpty() && T[stack.peek()] <= T[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) res[i] = 0;
            else res[i] = stack.peek() - i;
            stack.push(i);
        }
        return res;
    }
}

事實(shí)上就這道題而言這并不是一個(gè)好方法，因?yàn)樘崾疽呀?jīng)明確規(guī)定了數(shù)據(jù)范圍：

列表長(zhǎng)度的范圍是 [1, 30000]。每個(gè)氣溫的值的均為華氏度，都是在 [30, 100] 范圍內(nèi)的整數(shù)。

最多30000個(gè)數(shù)據(jù)量，數(shù)據(jù)非常小，入棧出棧，獲取棧頂元素，判斷棧是否空，在數(shù)據(jù)量很少的情況下這些函數(shù)反復(fù)調(diào)用，相對(duì)就占用了很多運(yùn)行時(shí)間，其最終評(píng)測(cè)運(yùn)行總時(shí)間為 109 ms。那么如何優(yōu)化？

由于所有數(shù)據(jù)值的范圍均在30到100之間，那么意為著按升序排列溫度的棧的大小 最大不會(huì)超過71（因?yàn)閺?0到100只有71個(gè)元素）。那就可以不用棧這個(gè)需要反復(fù)調(diào)用函數(shù)的數(shù)據(jù)結(jié)構(gòu)。直接用長(zhǎng)度為71的數(shù)組順序存入索引即可，定義一個(gè)指針，索引減一代替出棧，索引加一并賦值代替入棧，索引是否溢出代替判斷棧是否為空，無(wú)虛函數(shù)調(diào)用。

總運(yùn)行時(shí)間為 4ms，降低了105毫秒

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        int[] res = new int[len], stack = new int[71];
        int index = -1;
        for (int i = len - 1; i >= 0; i--) {
            while (index >= 0 && T[stack[index]] <= T[i]) {
                index--;
            }
            if(index >= 0) res[i] = stack[index] - i;
            stack[++index] = i;
        }
        return res;
    }
}

python并沒有隊(duì)列、棧這種數(shù)據(jù)結(jié)構(gòu)，因?yàn)閿?shù)組就可以做到先進(jìn)先出、后進(jìn)先出等操作。

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        tLen = len(T)
        stack = []
        res = [0] * tLen
        for i in range(tLen - 1, -1, -1):
            while stack and T[i] >= T[stack[-1]]:
                stack.pop()
            if stack: res[i] = stack[-1] - i
            stack.append(i)
        return res

歡迎關(guān)注微.信公.眾號(hào) 一起學(xué)習(xí)：愛寫B(tài)ug