【Hot100】739. 每日溫度

739. 每日溫度
給定一個整數數組 temperatures ，錶示每天的溫度，返回一個數組 answer ，其中 answer[i] 是指對於第 i 天，下一個更高溫度出現在幾天後。如果氣溫在這之後都不會昇高，請在該比特置用 0 來代替。

輸入: temperatures = [73,74,75,71,69,72,76,73]
輸出: [1,1,4,2,1,1,0,0]

題目理解：
對於輸入 73，它需要 經過一天 才能等到溫度的昇高，也就是在第二天的時候，溫度昇高到 74 ，所以對應的結果是 1。

對於輸入 74，它需要 經過一天 才能等到溫度的昇高，也就是在第三天的時候，溫度昇高到 75 ，所以對應的結果是 1。

對於輸入 75，它經過 1 天後發現溫度是 71，沒有超過它，繼續等，一直 等了四天，在第七天才等到溫度的昇高，溫度昇高到 76 ，所以對應的結果是 4 。

對於輸入 71，它經過 1 天後發現溫度是 69，沒有超過它，繼續等，一直 等了兩天，在第六天才等到溫度的昇高，溫度昇高到 72 ，所以對應的結果是 2 。

對於輸入 69，它 經過一天 後發現溫度是 72，已經超過它，所以對應的結果是 1 。

對於輸入 72，它 經過一天 後發現溫度是 76，已經超過它，所以對應的結果是 1 。

對於輸入 76，後續 沒有溫度 可以超過它，所以對應的結果是 0 。

對於輸入 73，後續 沒有溫度 可以超過它，所以對應的結果是 0 。

想法：針對每個溫度值 向後進行依次搜索 ，找到比當前溫度更高的值，這是最容易想到的辦法。

原理：是從左到右除了最後一個數其他所有的數都遍曆一次，最後一個數據對應的結果肯定是 0，就不需要計算。

遍曆的時候，每個數都去向後數，直到找到比它大的數，數的次數就是對應輸出的值。

class Solution {
    
    public int[] dailyTemperatures(int[] temperatures) {
    
        int len = temperatures.length;
        int[] res = new int[len];
        for(int i=0;i<len;i++){
    
            int cur = temperatures[i];
            if(cur < 100){
    
                for(int j=i+1;j<len;j++){
    
                    if(temperatures[j] > cur){
    
                        res[i] = j-i;
                        break;
                    }
                }
            }
        }
        return res;

    }

}

用棧來解决：
遞减棧 ：棧裏只有遞减元素。
遍曆整個數組，如果棧不空，且當前數字大於棧頂元素，那麼如果直接入棧的話就不是 遞减棧 ，所以需要取出棧頂元素，由於當前數字大於棧頂元素的數字，而且一定是第一個大於棧頂元素的數，直接求出下標差就是二者的距離。

繼續看新的棧頂元素，直到當前數字小於等於棧頂元素停止，然後將數字入棧，這樣就可以一直保持遞减棧，且每個數字和第一個大於它的數的距離也可以算出來。

class Solution {
    
    public int[] dailyTemperatures(int[] T) {
    
        Stack<Integer> stack = new Stack<>();
        int length = T.length;
        int[] result = new int[length];

        for (int i = 0; i < length; i++) {
    
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
    
                int pre = stack.pop();
                result[pre] = i - pre;
            }
            stack.add(i);

        }
        return result;
    }

   
}