每日温度
给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
解题思路
- 1、使用单调栈来解决问题。
- 2、遍历温度数组,对于每个温度:
-
如果栈为空,则将当前索引入栈;
-
如果当前温度大于栈顶温度,则出栈,并计算出栈温度对应的天数差值,并将结果存入结果数组;
-
如果当前温度小于等于栈顶温度,则将当前索引入栈,继续遍历。
- 3、遍历完成后,将栈中剩余元素对应的结果设置为0。
Java实现
public class DailyTemperatures {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 prevIndex = stack.pop();answer[prevIndex] = i - prevIndex;}//添加元素,下一个元素比较当前元素值stack.push(i);}return answer;}public static void main(String[] args) {DailyTemperatures solution = new DailyTemperatures();int[] temperatures = {73, 74, 75, 71, 69, 76,72, 73};int[] result = solution.dailyTemperatures(temperatures);System.out.print("Result: [");for (int i = 0; i < result.length; i++) {System.out.print(result[i]);if (i < result.length - 1) {System.out.print(", ");}}System.out.println("]");}
}
时间空间复杂度
-
时间复杂度:O(n),其中n为温度数组temperatures的长度。因为需要遍历温度数组一次,并且每个元素最多入栈一次。
-
空间复杂度:O(n),使用了一个额外的栈来存储温度数组的索引。