739. 每日温度

已解答

中等

给定一个整数数组 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

这个问题可以使用单调栈来解决。单调栈特别适合处理“下一个更大元素”这类问题。

算法思路

  1. 使用一个栈来存储温度的索引(而不是温度值本身)
  2. 遍历温度数组:

    • 当栈不为空且当前温度大于栈顶索引对应的温度时:

      • 弹出栈顶元素(找到了下一个更高温度)
      • 计算天数差 = 当前索引 - 栈顶索引
      • 将结果存入答案数组的对应位置
    • 将当前索引入栈
  3. 遍历结束后,栈中剩余的元素表示没有找到更高温度的日子,对应位置填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;
    }
}
分类: DS-Algo 标签: Java

评论

暂无评论数据

暂无评论数据

目录