P241 温度升高需要等待的天数

描述#

这个题目说的是，给你一个不为空的整数数组，数组中的元素表示每天的温度。你要计算出，对于每一天来说，温度升高需要等待的天数。如果对于某一天，未来不存在比它更高的温度，就把它对应的等待天数设置为 0。

比如说，给你的温度数组是：
1, 3, 1, 3, 2, 6
对于每一天来说，温度升高需要等待的天数是：
1, 4, 1, 2, 1, 0

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(1)
  public int[] dailyTemperaturesBruteForce(int[] T) {
    int n = T.length;
    int[] result = new int[n];
    for (int i = 0; i < n; ++i) {
      int j = i + 1;
      while (j < n && T[j] <= T[i]) ++j;
      if (j < n) result[i] = j - i;
      // else result[i] = 0;
    }
    return result;
  }

  // Time: O(n), Space: O(n)
  public int[] dailyTemperaturesStack(int[] T) {
    int n = T.length;
    int[] result = new int[n];
    Stack<Integer> st = new Stack<>();
    for (int i = 0; i < n; ++i) {
      while (!st.empty() && T[st.peek()] < T[i]) {
        int idx = st.pop();
        result[idx] = i - idx;
      }
      st.push(i);
    }
    // while (!st.empty()) result[st.pop()] = 0;
    return result;
  }

  // Time: O(n), Space: O(1)
  public int[] dailyTemperaturesSkip(int[] T) {
    int n = T.length;
    int[] result = new int[n];
    for (int i = n-2; i >= 0; --i) {
      int j = i + 1;
      while (T[j] <= T[i] && result[j] != 0) j += result[j];
      if (T[j] > T[i]) result[i] = j - i;
      // else result[i] = 0;
    }
    return result;
  }

}