Last Updated on 2022-12-18 by Clay
題目
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60] Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90] Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
題目給定一串代表每天溫度的數值陣列 temperatures，我們要另外儲存一個新的陣列，陣列中 i 的位置代表 temperatures[i] 的溫度隔幾天後會遇到更高的溫度；如果無論幾天後都沒有更高的溫度，則儲存 0。
解題紀錄
反向走訪
解這題的一個訣竅是反著走。最後一天的溫度一定沒有之後比它更高的溫度，所以紀錄為 0。之後，如果倒數第二天比最後一天的溫度低，則紀錄為 1......
總之，當我們要找一個溫度更高的日子時，一開始當然是直接跟當前位置的後一天比；然而若是後一天沒有比較高的溫度，則直接從後一天找到溫度更高日子的時間差，直接移動到比後一天溫度更高的日子去比較。
而這件事，我們會很理所當然地在反著走過來的時候做完，我們會知道比後一天溫度更高的第一個日子在哪裡，直接去比較那天就可以省下了中間很多無意義的比較過程。
反向走訪 複雜度
| Time Complexity | O(n) |
| Space Complexity | O(n) |
C++ 範例程式碼
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
// Init
vector<int> results(temperatures.size(), 0);
// Find the larger point at the left side
for (int i=temperatures.size()-2; i>=0; --i) {
int j = i + 1;
int steps = 1;
bool isFound = false;
// If `j` not out of boundary that we can explore
while (j < temperatures.size()) {
if (temperatures[i] >= temperatures[j]) {
if (results[j]) {
steps += results[j];
j += results[j];
}
else {
break;
}
}
else {
isFound = true;
break;
}
}
if (isFound) {
results[i] = steps;
}
}
return results;
}
};Python 範例程式碼
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
# Init
results = [0] * len(temperatures)
# Find the larger point at the left side
for i in range(len(temperatures)-2, -1, -1):
j = i + 1
steps = 1
isFound = False
# If `j` not out of boundary that we can explore
while j < len(temperatures):
if temperatures[i] >= temperatures[j]:
if results[j]:
steps += results[j]
j += results[j]
else:
break
else:
isFound = True
break
if isFound:
results[i] = steps
return results