Leetcode 739 每日溫度題解
[toc]
題目
請根據(jù)每日
氣溫列表，重新生成一個列表。對應(yīng)位置的輸出為：要想觀測到更高的氣溫，至少需要等待的天數(shù)。如果氣溫在這之后都不會升高，請在該位置用0來代替。來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/daily-temperatures/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
示例
例如，給定一個列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：氣溫 列表長度的范圍是 [1, 30000]。每個氣溫的值的均為華氏度，都是在 [30, 100] 范圍內(nèi)的整數(shù)。
思路與分析
方法1 暴力求解
氣溫列表的長度為不超過30000，暴力解法相當(dāng)于對于每個溫度都從左往右遍歷找到第一個溫度大于當(dāng)前溫度的下標(biāo)，因此時間復(fù)雜度為O(n^2)。在題目條件下是可以通過的。暴力解法的思路比較簡單，在這不做過多的贅述。
方法2 單調(diào)棧
分析暴力解法可以優(yōu)化的地方。通過對于示例進(jìn)行簡單的分析，我們可以發(fā)現(xiàn)，在找尋比溫度75大的下一個溫度的時候，71，69，72的目標(biāo)溫度結(jié)點也是可以一次得出的。因此，暴力解法的問題在于對于某些結(jié)點進(jìn)行了重復(fù)的計算。因此，優(yōu)化的方向就是利用已經(jīng)計算出的結(jié)果減少不必要的搜索（剪枝）或者減少重復(fù)的計算。對于剪枝，將在方法三中進(jìn)行解釋。對于如何減少重復(fù)的計算，通過前面的分析我們可以知道，當(dāng)后面的溫度先有結(jié)果時，應(yīng)該直接保存后面的結(jié)果。這種后面的溫度先處理的思想正好與棧的作用一致。
因此，在這引出了單調(diào)棧的概念。單調(diào)棧的含義，顧名思義，就是指棧中的元素是單調(diào)的。
例如，遞減棧指的就是棧中的元素是單調(diào)遞減的，例如75，71，69。當(dāng)我們遇到一個溫度大于此前的某個溫度的時候，我們已經(jīng)找到了某個結(jié)果。換言之，如果我們使用遞減棧來處理溫度。則當(dāng)當(dāng)前溫度大于棧頂?shù)臏囟葧r，棧中至少有一個元素找到了結(jié)果。為了保證棧是遞減的，我們將棧中溫度小于當(dāng)前溫度的棧都彈出，并保存結(jié)果，然后將當(dāng)前溫度入棧。當(dāng)所有溫度遍歷完成后，我們就得到了結(jié)果。
注意，因為題目要求的是位置（坐標(biāo)），因此壓入棧中的元素實際上是溫度的索引。索引的差值就是下一個溫度升高的天數(shù)。
代碼
class Solution {
public int[] dailyTemperatures(int[] T) {
int n = T.length;
//用于保存結(jié)果
int[] ans = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
//若棧不為空且當(dāng)前溫度大于棧頂溫度，說明棧頂溫度的結(jié)果已經(jīng)找到，
//將棧頂溫度彈出并保存結(jié)果
while (!stack.empty() && T[i] > T[stack.peek()]) {
ans[stack.peek()] = i - stack.peek();
stack.pop();
}
stack.push(i);
}
return ans;
}
}
時間復(fù)雜度O(n)，每個溫度遍歷一次。
空間復(fù)雜度O(n)，用于單調(diào)棧，最壞情況下棧的長度為n。
方法3 剪枝
通過分析前面的示例，我們注意到中間有重復(fù)的計算過程。更進(jìn)一步，中間的重復(fù)計算是由于從左往右的順序造成的。例如在計算溫度75的結(jié)果時，我們需要遍歷71，69，72，76。而在這個過程中，71，69，72的結(jié)果其實已經(jīng)知道了。但當(dāng)我們計算71的結(jié)果時，我們?nèi)孕柙L問69，72。那么，如果我們從右往左計算呢？
我們可以發(fā)現(xiàn)，最后一個溫度的結(jié)果肯定是0，倒數(shù)第二個溫度的結(jié)果取決于它右邊的溫度（即倒數(shù)第一個溫度）。倒數(shù)第三個溫度的結(jié)果取決于倒數(shù)第一，第二個溫度......。而右邊溫度的結(jié)果我們是已知的，因此，我們可以利用這個結(jié)果來進(jìn)行剪枝。舉個例子，76的下一個溫度是72，72小于76，而72的結(jié)果是0，表示右邊沒有比72大的溫度，因此可以提前結(jié)束搜索，76的結(jié)果一定是0。72的下一個溫度是76，則72的結(jié)果為1。75的下一個溫度是71，小于75，下一個比71大的溫度是71的結(jié)果72，小于75，下一個比72大的是72的結(jié)果76,大于75.因此75的結(jié)果就是76的下標(biāo)減去75的下標(biāo)。
綜上所述，在處理當(dāng)前溫度時有三種情況。
- 下一個溫度大于當(dāng)前溫度，計算結(jié)果。.
- 下一個溫度的結(jié)果為0， 結(jié)果為0（因為右邊以及沒有比下一個溫度大的溫度）
- 將比較對象移到下一個溫度的結(jié)果，重復(fù)第一步。
代碼
class Solution {
public int[] dailyTemperatures(int[] T) {
int n = T.length;
int[] ans = new int[n];
//倒數(shù)第一個溫度的結(jié)果為0，直接從倒數(shù)第二個結(jié)點搜索
for (int i = n - 2; i >= 0; i--) {
//從下一個結(jié)點開始查找
int j = i + 1;
while (j < n) {
if (T[j] > T[i]) {
//找到結(jié)果，計算結(jié)果并提前結(jié)束當(dāng)前結(jié)點的計算
ans[i] = j - i;
break;
} else if (ans[j] == 0) {
//表明右邊已經(jīng)不可能有大于當(dāng)前溫度的溫度，直接結(jié)束搜索。
break;
} else {
//看下一個更大的溫度是否是結(jié)果
j += ans[j];
}
}
}
return ans;
}
}
