根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高的天数。如果之后都不会升高，请输入 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的都是 [30, 100] 范围内的整数。

 

思路：

1.首先想到暴力比较：两层for循环

//暴力比较 O(n^2)
	public static int[] dailyTemperatures(int[] T) {
		int[] res = new int[T.length];
		res[res.length - 1] = 0;
		for (int i = 0; i < res.length - 1; i++) {
			for (int j = i + 1; j < res.length; j++) {
				if (T[j] > T[i]) {
					res[i] = j - i;
					break;
				} else if (j == res.length - 1) {
						res[i] = 0;
					}
				
			}
		}
		return res;
	}

时间复杂度较大

2.用栈保存数组下标，每次弹出下标  找到第一个比该下标对应元素大的位置

        //用一个栈保存数组的下标   O(n)
		public static int[] dailyTemperatures(int[] T) {
			Stack<Integer> stack =new Stack<>();  //保存数组下标
			int[] res = new int[T.length];
			Arrays.fill(res, 0);
			for (int i = 0; i < res.length; i++) {
				while (!stack.isEmpty()&&T[i]>T[stack.peek()]) {
					int resIndex=stack.pop();
					res[resIndex]=i-resIndex;
				}
				//每次进来都把下标存储
				stack.push(i);
			}
			return res;
		}