请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 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]

提示：

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

  1. class Solution {
  2.     /**
  3.     本题采用单调栈解决，具体的使用单调递减栈，因为我们是遇到第一个比栈顶元素大的值就出栈，我们栈里面存储下标值
  4.      */
  5.     public int[] dailyTemperatures(int[] temperatures) {
  6.         int n = temperatures.length;
  7.         Deque<Integer> stack = new LinkedList<>();
  8.         int[] res = new int[n];
  9.         for (int i = 0; i < n; ++i) {
  10.             while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
  11.                 int idx = stack.poll();
  12.                 res[idx] = i - idx;
  13.             }
  14.             stack.push(i);
  15.         }
  16.         return res;
  17.     }
  18. }

数组模拟

  1. class Solution {
  2.     int[] st;
  3.     int tt;
  4.     public int[] dailyTemperatures(int[] temperatures) {
  5.         int n = temperatures.length;
  6.         int[] res = new int[n];
  7.         st = new int[n + 1];
  8.         for (int i = 0; i < n; ++i) {
  9.             while (tt > 0 && temperatures[st[tt]] < temperatures[i]) {
  10.                 int tem = st[tt--];
  11.                 res[tem] = i - tem;
  12.             }
  13.             st[++tt] = i;
  14.         }
  15.         return res;
  16.     }
  17. }