每日温度

发表于 更新于 分类于 本文字数： 287 阅读时长 ≈ 3 分钟

题目描述

Leetcode题目链接：739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，
其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。
如果气温在这之后都不会升高，请在该位置用 0 来代替。

1
2
3
4
5
6
7
8
9
10
11
12
示例 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. 暴力两层for循环，时间复杂度：O(n^2)
  2. 使用栈，保存的元素为数组的索引index。一层循环遍历，
    反复比较当天温度与栈顶元素对应的温度，如果大于当天温度则出栈；
    否则在栈保存当天温度的索引index，让栈中的元素对应的温度呈现单调递增。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 解法2源码
public static int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] res = new int[n];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        while (!stack.empty()) {
            Integer peek = stack.peek();
            if (temperatures[peek] < temperatures[i]) {
                stack.pop();
                res[peek] = i - peek;
            } else {
                break;
            }
        }
        stack.push(i);
    }
    return res;
}

项目地址