每日温度
给定一个整数数组 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)，使用了一个额外的栈来存储温度数组的索引。
