739. 每日溫度
請根據(jù)每日 氣溫 列表球榆，重新生成一個(gè)列表娃兽。對應(yīng)位置的輸出為：要想觀測到更高的氣溫菇民，至少需要等待的天數(shù)。如果氣溫在這之后都不會(huì)升高投储，請?jiān)谠撐恢糜?0 來代替第练。
例如，給定一個(gè)列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]玛荞，你的輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]娇掏。
方法1：暴力解法
雙重循環(huán)遍歷即可
public int[] dailyTemperatures(int[] T) {
int[] res = new int[T.length];
for (int i = 0; i < T.length - 1; i++) {
for (int j = i + 1; j < T.length; j++) {
if (T[j] > T[i]) {
res[i] = j - i;
break;
}
}
}
return res;
}
方法2：單調(diào)棧
維護(hù)一個(gè)單調(diào)遞減棧，棧中存放氣溫?cái)?shù)組的下標(biāo)勋眯。所謂單調(diào)遞減棧婴梧，就是棧的底部到頂部是單調(diào)遞減的。從頭遍歷氣溫?cái)?shù)組T客蹋，若棧為空塞蹭，直接將數(shù)組下標(biāo)入棧；若棧不為空嚼酝，并且當(dāng)前遍歷到的下標(biāo)對應(yīng)的溫度T[i] 大于棧頂下標(biāo)對應(yīng)的溫度浮还，那么說明這個(gè)溫度是棧頂元素的下一個(gè)更高的溫度，將棧頂元素彈出闽巩，兩者下標(biāo)的差值即為所求的天數(shù)钧舌，注意這個(gè)判斷應(yīng)該用while循環(huán)。
時(shí)間復(fù)雜度O(N)
public int[] dailyTemperatures(int[] T) {
int[] res = new int[T.length];
//單調(diào)遞減棧
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < T.length; i++) {
while (!stack.isEmpty() && T[i] > T[stack.peekLast()]) {
int top = stack.peekLast();
res[stack.pollLast()] = i - top;
}
stack.addLast(i);
}
return res;
}
