739. 每日温度

image.png

暴力法

对于每个温度都往后遍历，直到找到大于当前温度的值

执行用时：1372 ms, 在所有 Java 提交中击败了8.55%的用户 内存消耗：48.6 MB, 在所有 Java 提交中击败了42.87%的用户

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

辅助栈法

执行用时：35 ms, 在所有 Java 提交中击败了47.96%的用户 内存消耗：47.7 MB, 在所有 Java 提交中击败了70.63%的用户

可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。
如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。
正向遍历温度列表。对于温度列表中的每个元素 temperatures[i]，如果栈为空，则直接将 i 进栈，如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 temperatures[prevIndex] 和当前温度 temperatures[i]，如果 temperatures[i] > temperatures[prevIndex]，则将 prevIndex 移除，并将 prevIndex 对应的等待天数赋为 i - prevIndex，重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。


public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] resArr = new int[length];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < length; i++) {
            int cur = temperatures[i];
            while (!stack.isEmpty() && cur > temperatures[stack.peek()]) {
                Integer preIdx = stack.pop();
                resArr[preIdx] = i - preIdx;
            }
            stack.push(i);
        }
        return resArr;
    }
}