请根据每日 气温
列表 temperatures
,重新生成一个列表,要求其对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0
来代替。
示例 1:
输入: temperatures
= [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90] 输出: [1,1,0]
提示:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
注意:本题与主站 739 题相同: https://leetcode-cn.com/problems/daily-temperatures/
单调栈常见模型:找出每个数左/右边离它最近的且比它大/小的数。模板:
stk = []
for i in range(n):
while stk and check(stk[-1], i):
stk.pop()
stk.append(i)
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
res = [0] * len(temperatures)
stk = []
for i, t in enumerate(temperatures):
while stk and temperatures[stk[-1]] < t:
j = stk.pop()
res[j] = i - j
stk.append(i)
return res
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
Deque<Integer> stk = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
while (!stk.isEmpty() && temperatures[stk.peek()] < temperatures[i]) {
int j = stk.pop();
res[j] = i - j;
}
stk.push(i);
}
return res;
}
}
class Solution {
public:
vector<int> dailyTemperatures(vector<int> &temperatures) {
int n = temperatures.size();
vector<int> res(n);
stack<int> stk;
for (int i = 0; i < n; ++i)
{
while (!stk.empty() && temperatures[stk.top()] < temperatures[i])
{
res[stk.top()] = i - stk.top();
stk.pop();
}
stk.push(i);
}
return res;
}
};
func dailyTemperatures(temperatures []int) []int {
res := make([]int, len(temperatures))
var stk []int
for i, t := range temperatures {
for len(stk) > 0 && temperatures[stk[len(stk)-1]] < t {
j := stk[len(stk)-1]
res[j] = i - j
stk = stk[:len(stk)-1]
}
stk = append(stk, i)
}
return res
}