一、題目大意
標簽: 堆疊和佇列
https://leetcode.cn/problems/daily-temperatures
給定一個整數陣列 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 <= 105
-
30 <= temperatures[i] <= 100
二、解題思路
什么是單調堆疊？單調堆疊通過維持堆疊內值的單調遞增（遞減）性，在整體O(n)的時間內處理需要大小比較的問題，
思路：可以維持一個單調遞減的堆疊，表示每天的溫度，為了方便計算天數差，這里存放位置（即日期）而非溫度本身，從左向右遍歷溫度陣列，對于每個日期p，如果p的溫度比堆疊頂存盤位置q的溫度高，則我們取出q，并記錄q需要等待的天數p-q；重復這一程序，直到p的溫度小于等于堆疊頂位置的溫度或空堆疊時，我們將p插入堆疊頂，然后考慮下一天，在這個程序中堆疊內陣列永遠保持單調遞減，避免了使用排序進行比較，最后若堆疊內剩余一些日期，則說明它們之后都沒有出現更暖和的日期，
三、解題方法
3.1 Java實作
public class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] ans = new int[temperatures.length];
Stack<Integer> desStack = new Stack<>();
for (int i = 0; i < temperatures.length; i++) {
while (!desStack.isEmpty()) {
int preIndex = desStack.peek();
if (temperatures[i] <= temperatures[preIndex]) {
break;
}
desStack.pop();
ans[preIndex] = i - preIndex;
}
desStack.push(i);
}
return ans;
}
}
四、總結小記
- 2022/8/10 下雨、下雪本是很好玩的事，大了之后也不盡然，出行、生產、作業都會受到影響
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501503.html
標籤：其他