力扣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]

这是最容易想到的办法，但是时间复杂度为O(n^2),超出了时间限制

class Solution { public int[] dailyTemperatures(int[] temperatures) { int[] ints =new int[temperatures.length]; int temp=1; for (int i = 0; i <= temperatures.length - 1; i++) { for (int j = i+1; j <= temperatures.length-1; j++) { if (temperatures[i]>=temperatures[j]){  temp++; }else {  ints[i]=temp;  break; } } temp=1; } return ints; }}

所以我转变一下思路 用栈去存储

class Solution { public int[] dailyTemperatures(int[] temperatures) { int[] result=new int[temperatures.length]; Stack<Integer> stack = new Stack<Integer>(); for (int i = 0; i < result.length; i++) { result[i]=0; } for (int i = 0; i < result.length; i++) { while(!stack.isEmpty() && temperatures[stack.peek()]<temperatures[i]){  int num=stack.pop();  result[num]=i-num; } stack.push(i); } return result;}}

这样时间复杂度就降为o(n)了