每日温度
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 100 ms, 内存: 22.9 MB
/*
题目思路:
Java Stream 主要用于处理集合类数据,但在这个问题上,由于需要处理每个元素与之前的元素之间的关系,Stream 并不是特别合适。
然而,我们可以利用一些辅助数据结构,例如栈,来实现这个功能。
*/
import java.util.stream.IntStream;
import java.util.Stack;
public class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] result = new int[n];
Stack<Integer> stack = new Stack<>();
IntStream.range(0, n).forEach(i -> {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int index = stack.pop();
result[index] = i - index;
}
stack.push(i);
});
return result;
}
}
解释
方法:
此题解采用了单调栈的方法。单调栈用于维护一个元素索引的栈,索引对应的温度值是单调递减的。遍历温度列表,对于每一个温度,如果当前温度大于栈顶温度,说明找到了栈顶元素的第一个更高的温度,此时将栈顶元素索引弹出,并计算当前索引与栈顶索引的差值,作为答案数组对应位置的值。如果当前温度小于等于栈顶温度,或者栈为空,则把当前温度的索引压入栈。最后,栈中剩余的索引对应的温度值在右侧没有更高的温度值,答案数组默认已经初始化为0,因此不需要额外操作。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在单调栈中,为什么选择栈顶元素的温度必须保持单调递减?
▷🦆
如果当前温度等于栈顶温度时,为什么没有处理这种情况,它会影响结果吗?
▷🦆
代码中的while循环会在什么条件下结束?如果温度列表是单调递增的,栈的行为会怎样?
▷