代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
请根据每日 气温
列表 temperatures
,重新生成一个列表,要求其对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0
来代替。
示例 1:
temperatures
示例 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/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]:
ans = [0] * len(temperatures)
stk = []
for i, t in enumerate(temperatures):
while stk and temperatures[stk[-1]] < t:
j = stk.pop()
ans[j] = i - j
stk.append(i)
return ans
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
stk = []
ans = [0] * n
for i in range(n - 1, -1, -1):
while stk and temperatures[stk[-1]] <= temperatures[i]:
stk.pop()
if stk:
ans[i] = stk[-1] - i
stk.append(i)
return ans
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] ans = 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();
ans[j] = i - j;
}
stk.push(i);
}
return ans;
}
}
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
Deque<Integer> stk = new ArrayDeque<>();
int[] ans = new int[n];
for (int i = n - 1; i >= 0; --i) {
while (!stk.isEmpty() && temperatures[stk.peek()] <= temperatures[i]) {
stk.pop();
}
if (!stk.isEmpty()) {
ans[i] = stk.peek() - i;
}
stk.push(i);
}
return ans;
}
}
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n);
stack<int> stk;
for (int i = 0; i < n; ++i) {
while (!stk.empty() && temperatures[stk.top()] < temperatures[i]) {
ans[stk.top()] = i - stk.top();
stk.pop();
}
stk.push(i);
}
return ans;
}
};
class Solution {
public:
vector<int> dailyTemperatures(vector<int> &temperatures) {
int n = temperatures.size();
vector<int> ans(n);
stack<int> stk;
for (int i = n - 1; ~i; --i) {
while (!stk.empty() && temperatures[stk.top()] <= temperatures[i]) stk.pop();
if (!stk.empty()) ans[i] = stk.top() - i;
stk.push(i);
}
return ans;
}
};
func dailyTemperatures(temperatures []int) []int {
ans := 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]
ans[j] = i - j
stk = stk[:len(stk)-1]
}
stk = append(stk, i)
}
return ans
}
func dailyTemperatures(temperatures []int) []int {
n := len(temperatures)
ans := make([]int, n)
var stk []int
for i := n - 1; i >= 0; i-- {
for len(stk) > 0 && temperatures[stk[len(stk)-1]] <= temperatures[i] {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
ans[i] = stk[len(stk)-1] - i
}
stk = append(stk, i)
}
return ans
}
倒序:
function dailyTemperatures(temperatures: number[]): number[] {
const n = temperatures.length;
const res = new Array(n);
const stack = [];
for (let i = n - 1; i >= 0; i--) {
while (
stack.length !== 0 &&
temperatures[stack[stack.length - 1]] <= temperatures[i]
) {
stack.pop();
}
res[i] = stack.length === 0 ? 0 : stack[stack.length - 1] - i;
stack.push(i);
}
return res;
}
正序:
function dailyTemperatures(temperatures: number[]): number[] {
const n = temperatures.length;
const res = new Array(n).fill(0);
const stack = [];
for (let i = 0; i < n; i++) {
const temperature = temperatures[i];
while (
stack.length !== 0 &&
temperatures[stack[stack.length - 1]] < temperature
) {
const j = stack.pop();
res[j] = i - j;
}
stack.push(i);
}
return res;
}
倒序:
impl Solution {
pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
let n = temperatures.len();
let mut res = vec![0; n];
let mut stack = Vec::new();
for i in (0..n).rev() {
while !stack.is_empty() && temperatures[*stack.last().unwrap()] <= temperatures[i] {
stack.pop();
}
res[i] = if stack.is_empty() {
0
} else {
(stack.last().unwrap() - i) as i32
};
stack.push(i);
}
res
}
}
正序:
impl Solution {
pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
let n = temperatures.len();
let mut res = vec![0; n];
let mut stack = Vec::new();
for i in 0..n {
while !stack.is_empty() && temperatures[*stack.last().unwrap()] < temperatures[i] {
let j = stack.pop().unwrap();
res[j] = (i - j) as i32;
}
stack.push(i);
}
res
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。