這道題主要是找規律，優化的時候可以利用數據結構的特性（數組和棧）。
原題
根據每日氣溫列表，請重新生成一個列表，對應位置的輸入是你需要再等待多久，溫度才會升高超過該日的天數。如果之後都不會升高，請在該位置用 0 來代替。
例如，給定一個列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應該是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：氣溫 列表長度的範圍是 [1, 30000]。每個氣溫的值的均為華氏度，都是在 [30, 100] 範圍內的整數。
原題url：https://leetcode-cn.com/problems/daily-temperatures/
解題
優先隊列
如果正向思考的話，就是從前向後遍歷，將溫度存儲在一個優先級隊列中（小頂堆），隊列中的結構需要記錄溫度和天數。
遍歷時需要找到隊列中最小的值是否大於當前溫度，如果大於，則更新結果；如果小於，則將當前記錄放入隊列中。
接下來看看代碼：
<code>class Solution {
public int[] dailyTemperatures(int[] T) {
// 以溫度為排序依據的小頂堆，溫度越低越靠前
PriorityQueue<node> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.temperature));
for (int index = 0; index < T.length; index++) {
Node node = new Node();
node.temperature = T[index];
node.index = index;
// 放入隊列中
queue.add(node);
// 取隊列中最小的元素
Node newNode = queue.peek();
// 如果隊列中最低溫度就是當前溫度
if (newNode.temperature == node.temperature) {
// 說明queue中沒有比當前溫度低的天
continue;
}
// 最低溫度比當前低，滿足情況
while (newNode.temperature < node.temperature) {
// 更新T，並且移除
T[newNode.index] = node.index - newNode.index;
queue.remove();
newNode = queue.peek();
}
}
// 隊列中剩餘的節點，都對應0
Iterator<node> iterator = queue.iterator();
while (iterator.hasNext()) {
Node node = iterator.next();
T[node.index] = 0;
}
return T;
}
class Node {
int temperature;
int index;
}
}/<node>/<node>/<code> 提交OK，時間複雜度為O(n)，但小頂堆的更新也是需要時間的，因此還是有可以優化的地方。
數組
因為題目中給出了：每個氣溫的值的均為華氏度，都是在 [30, 100] 範圍內的整數，所以我們可以用一個長度為100的數組存儲氣溫對應的天數。
這樣我們就需要從後向前遍歷了，將氣溫對應的天數記錄在數組中，這樣每向前遍歷一個，就遍歷一次這個長度為100的數組，如果有比當前溫度高的，則更新結果，否則就記為0。
雖然每次都要遍歷一次長度為100的數組，但因為數組查詢的時間複雜度為O(1)，所以速度是很快的。接下來我們看看代碼：
<code>class Solution {
public int[] dailyTemperatures(int[] T) {
// 最終結果
int[] result = new int[T.length];
// 因為溫度不超過100度，所以溫度對應的天數存儲在這個數組中
int[] next = new int[101];
Arrays.fill(next, Integer.MAX_VALUE);
// 從後向前遍歷
for (int i = T.length - 1; i >= 0; --i) {
// 比當前溫度更高的下標
int warmerIndex = Integer.MAX_VALUE;
// 從next數組中查找比當前溫度高的天數
for (int t = T[i] + 1; t <= 100; ++t) {
// 找出天數最小的一個
if (next[t] < warmerIndex) {
warmerIndex = next[t];
}
}
// 如果有找到，則更新result
if (warmerIndex < Integer.MAX_VALUE) {
result[i] = warmerIndex - i;
}
// 在next數組中記錄當前的溫度
next[T[i]] = i;
}
return result;
}
}/<code>提交OK，這裡其實就夠了，但有沒有其他更方便的數據結構呢？
棧
我們主要想知道的，就是最近的比當前溫度高的天數，這樣的需求，感覺棧應該是可以滿足的，因為先進後出。
我們還是從後向前遍歷，在棧中存儲氣溫的天數，當前遍歷到的溫度，如果比棧頂的存儲的天數對應的溫度高，那麼棧中存儲的是沒有意義的；如果比它低，那麼就可以更新結果了。
接下來看看代碼：
<code>class Solution {
public int[] dailyTemperatures(int[] T) {
// 用棧存儲溫度的下標
Stack<integer> stack = new Stack<>();
// 最終的結果
int[] result = new int[T.length];
// 從後向前遍歷
for (int i = T.length - 1; i >= 0; i--) {
// 如果當前溫度大於棧頂的溫度
while (!stack.isEmpty() && T[i] >= T[stack.peek()]) {
// 因為當前溫度比棧頂存儲的溫度高，
// 棧頂元素也沒有存儲的意義，所以出棧
stack.pop();
}
// 如果棧為空，則結果為0
// 如果棧不為空，則用當前棧頂存儲的溫度
result[i] = stack.isEmpty() ? 0 : (stack.peek() - i);
// 讓當前的溫度入棧
stack.push(i);
}
return result;
}
}/<integer>/<code>提交OK，時間複雜度和上面的方法相同，但空間複雜度理論上是會比上面小的。
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要是找規律，優化的時候可以利用數據結構的特性（數組和棧）。
有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號，說不定會有意外的驚喜。
https://death00.github.io/
閱讀更多 健程之道 的文章
