LeetCode 739. 每日温度

解法一

双循环

  • 时间复杂度O(n²)
  • 空间复杂度O(n)
public int[] dailyTemperatures(int[] T) {
       int[] num = new int[T.length];
       for (int i = 0; i < T.length - 1; i++) {
           for (int j = i + 1; j < T.length; j++) {
               if (T[i] < T[j]) {
                   num[i] = j - i;
                   break;
               }
               num[i] = 0;
           }
       }
       return num;
   }

解法二

反向循环

  • 时间复杂度O(nlgn)（我猜的
  • 空间复杂度O(n)
public int[] dailyTemperatures(int[] T) {
        int[] result = new int[T.length];
        for (int i = T.length - 2; i >= 0; i--) {
            for (int j = i + 1; j < T.length; j+=result[j]) {
                if (T[i] < T[j]) {
                    result[i] = j - i;
                    break;
                }
                if (result[j] == 0) {
                    break;
                }
            }
        }
        return result;
    }

解法三

单调栈

  • 时间复杂度O(n)
  • 空间复杂度O(n)
public int[] dailyTemperatures(int[] T) {
        Deque<Integer> stack = new ArrayDeque<>();
        int result[] = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int pop = stack.pop();
                result[pop] = i - pop;
            }
            stack.push(i);
        }
        return result;
    }