LeetCode 739. 每日温度 [Hot 100] —— 单调栈
已解答
中等
给定一个整数数组 temperatures
,表示每天的温度,返回一个数组 answer
,其中 answer[i]
是指对于第 i
天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 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
这个问题可以使用单调栈来解决。单调栈特别适合处理“下一个更大元素”这类问题。
算法思路
- 使用一个栈来存储温度的索引(而不是温度值本身)
遍历温度数组:
当栈不为空且当前温度大于栈顶索引对应的温度时:
- 弹出栈顶元素(找到了下一个更高温度)
- 计算天数差 = 当前索引 - 栈顶索引
- 将结果存入答案数组的对应位置
- 将当前索引入栈
- 遍历结束后,栈中剩余的元素表示没有找到更高温度的日子,对应位置填0
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[i] >temperatures[stack.peek()]) {
int prevIdx = stack.pop();
answer[prevIdx] = i-prevIdx;
}
stack.push(i);
}
return answer;
}
}
版权申明
本文系作者 @xiin 原创发布在To Future$站点。未经许可,禁止转载。
暂无评论数据