【力扣】739. 每日溫度

給定一個整數數組 temperatures ，表示每天的溫度，返回一個數組 answer ，其中 answer[i] 是指對于第 i 天，下一個更高溫度出現在幾天后。如果氣溫在這之后都不會升高，請在該位置用 0 來代替。

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

示例 2:
輸入: temperatures = [30,40,50,60]
輸出: [1,1,1,0]

示例 3:
輸入: temperatures = [30,60,90]
輸出: [1,1,0]

提示：
1 <= temperatures.length <= $10^5$
30 <= temperatures[i] <= 100

題解

??通常是一維數組，要尋找任一個元素的右邊或者左邊第一個比自己大或者小的元素的位置，此時就要想到可以用單調棧。時間復雜度為O(n)。
??單調棧的本質是空間換時間，因為在遍歷的過程中需要用一個棧來記錄右邊第一個比當前元素高的元素，優點是整個數組只需要遍歷一次。更直白來說，就是用一個棧來記錄遍歷過的元素，因為遍歷數組的時候，不知道之前都遍歷了哪些元素，以至于遍歷一個元素找不到是不是之前遍歷過一個更小的，所以需要用一個容器（這里用單調棧）來記錄我們遍歷過的元素。

使用單調棧的時候首先要明確如下幾點：

• 單調棧里存放的元素是什么？
  單調棧里只需要存放元素的下標 $i$ 就可以了，如果需要使用對應的元素，直接 $T[i]$ 就可以獲取。

• 單調棧里元素是遞增呢？ 還是遞減呢？（從棧頭到棧底的順序）
  如果求一個元素右邊第一個更大元素，單調棧就是遞增的，如果求一個元素右邊第一個更小元素，單調棧就是遞減的。

??本題其實就是找找到一個元素右邊第一個比自己大的元素，此時就應該想到用單調棧。

class Solution {
public static int[] dailyTemperatures(int[] temperatures) {//單調棧只存放下標Stack<Integer> stack = new Stack<>();int[] result = new int[temperatures.length];//先放入第一個元素下標stack.push(0);for (int i = 1; i < temperatures.length; i++) {//情況1：小于if (temperatures[i] < temperatures[stack.peek()]) { stack.push(i);}//情況2：等于else if (temperatures[i] == temperatures[stack.peek()]){  stack.push(i);}//情況3：大于else {while (!stack.isEmpty() && (temperatures[i] > temperatures[stack.peek()])) { int index =  stack.peek();result[index] = i - index;stack.pop();}stack.push(i);}}return result;}
}

雙端隊列實現：

class Solution {
public static int[] dailyTemperatures(int[] temperatures) {//單調棧只存放下標Deque<Integer> stack = new LinkedList<>();int[] result = new int[temperatures.length];stack.push(0);for (int i = 1; i < temperatures.length; i++) {//情況1：小于if (temperatures[i] < temperatures[stack.peek()]) { stack.push(i);}//情況2：等于else if (temperatures[i] == temperatures[stack.peek()]){  stack.push(i);}//情況3：大于else {while (!stack.isEmpty() && (temperatures[i] > temperatures[stack.peek()])) { int index =  stack.peekFirst();result[index] = i - index;stack.pop();}stack.push(i);}}return result;}
}