題目

請根據(jù)每日?氣溫?列表?temperatures?，重新生成一個列表，要求其對應位置的輸出為：要想觀測到更高的氣溫，至少需要等待的天數(shù)。如果氣溫在這之后都不會升高，請在該位置用?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 <= 105
• 30 <=?temperatures[i]?<= 100

注意：本題與主站 739?題相同：?力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術成長平臺

LCR 038. 每日溫度 - 力扣（LeetCode）

題解

思路一：暴力解法，因為溫度是從30-100.使用一個sum數(shù)組來存儲所有出現(xiàn)的溫度，對應的距離當前元素最近的下標。從后向前遍歷原始數(shù)組。sum[i]，i表示溫度，sum[i]表示在原數(shù)組中的下標。因為是后序遍歷的，因此一定是出現(xiàn)在后面的更高溫度。

代碼：

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] sum = new int[101];int[] ans=new int[temperatures.length];Arrays.fill(sum,Integer.MAX_VALUE);for(int i=temperatures.length-1;i>=0;i--) {int index=Integer.MAX_VALUE;for(int j=temperatures[i]+1;j<101;j++) {if(sum[j]<index) {index=sum[j];}}if(index<Integer.MAX_VALUE) ans[i]=index-i;//一定要記得-i，因為是從i開始算第多少個溫度更高sum[temperatures[i]]=i;}return ans;}
}

思路二：單調棧思想，棧中存儲下標，棧中數(shù)據(jù)所代表的溫度從棧底到棧頂是從高到低的，從前向后遍歷原始數(shù)組。棧不空時，當有溫度元素大于棧頂元素時，取出棧頂元素，更新ans[棧內index]（代表的是還需要幾天才升高）=當前index-棧內index；溫度小于棧頂或者棧空時，直接入棧，最后將所有的棧內殘留ans[index]=0。

代碼：

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] ans = new int[temperatures.length];Deque<Integer> stack = new ArrayDeque<Integer>();for (int i = 0; i < length; i++) {int temperature = temperatures[i];while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {int prevIndex = stack.pop();ans[prevIndex] = i - prevIndex;}stack.push(i);}return ans;}
}