LeetCode 739：每日温度 Daily Temperatures

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## LeetCode 739：每日温度 Daily Temperatures

### 题目：

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

### 解题思路：

栈为空，res[7] = 0 ,73所在索引7入栈。stack = [7]

栈顶对应索引7的温度T[7]=76,76>73,索引7出栈,此时栈为空，res[6] = 0。索引6入栈，stack = [6]

栈顶对应索引6的温度T[6]=76,72<76,满足要求,当前索引5入栈。res[5] = 栈顶索引6 - 当前索引5 = 1, stack = [6,5]

栈顶对应索引5的温度T[5]=72,69<72,满足要求,当前索引4入栈。res[4] = 栈顶索引5-当前索引4=1, stack = [6,5,4]

栈顶对应索引的温度T[4]=69,71>69,栈顶元素出栈。stack = [6,5]
栈顶对应索引的温度T[5]=72,满足要求,当前索引3入栈。res[3] = 栈顶索引5-当前索引3=2, stack = [6,5,3]

栈顶对应索引的温度T[3]=71,75>71,栈顶元素出栈。stack = [6,5]
栈顶对应索引的温度T[5]=72,75>72,栈顶元素出栈。stack = [6]
栈顶对应索引的温度T[6]=76,75<76,满足要求，当前索引2入栈。res[2] = 栈顶索引6-当前索引2=4, stack = [6,2]

栈顶对应的温度T[2]=75,满足要求,当前索引1入栈。res[1] = 2-1=1, stack = [6,2,1]

栈顶对应的温度T[1]=74,满足要求,当前索引0入栈。res[0] = 1-0=1, stack = [6,2,1,0]

### Java：

class Solution {
public int[] dailyTemperatures(int[] T) {
int len=T.length;
int[] res = new int[len];
Stack<Integer> stack = new Stack<>();//初始化栈
for (int i = len - 1; i >= 0; i--) {
while (!stack.isEmpty() && T[stack.peek()] <= T[i]) {
stack.pop();
}
if (stack.isEmpty()) res[i] = 0;
else res[i] = stack.peek() - i;
stack.push(i);
}
return res;
}
}

### 优化后：

class Solution {
public int[] dailyTemperatures(int[] T) {
int len = T.length;
int[] res = new int[len], stack = new int[71];
int index = -1;
for (int i = len - 1; i >= 0; i--) {
while (index >= 0 && T[stack[index]] <= T[i]) {
index--;
}
if(index >= 0) res[i] = stack[index] - i;
stack[++index] = i;
}
return res;
}
}

### Python：

python并没有队列、栈这种数据结构，因为数组就可以做到先进先出、后进先出等操作。

class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
tLen = len(T)
stack = []
res = [0] * tLen
for i in range(tLen - 1, -1, -1):
while stack and T[i] >= T[stack[-1]]:
stack.pop()
if stack: res[i] = stack[-1] - i
stack.append(i)
return res

+ 关注