题目

• 概述：给定一个气温列表，让你求每个气温值与下一个更大的气温值之间的距离，如果找不到下一个更大的气温值，则距离为0

• 输入：一个气温列表，长度范围为[1, 30000]

• 输入子项：一个整数气温值，范围为[30，100]

• 输出：每个气温值到下一个更大气温值的距离，若不存在下一个更大的，则距离为0

• 出处：https://leetcode-cn.com/problems/daily-temperatures/

思路

• 寻找下一个更大的问题，可以逆序思考

• 气温列表的最后一项必定没有下一个更大的气温值，所以距离为0

• 对于气温列表的每一项，假设它之后的气温值到下一个更大的气温值的距离都已求出，那么

  1. 如果当前的气温值小于下一个气温值，则当前气温值到下一个更大气温值的距离为1
  2. 如果当前的气温值大于等于下一个气温值，记下一个更大气温值到它的下一个更大气温值的距离为d，它的下一个更大气温值为t，则当前气温值到下一个更大气温值的距离等于dis：
     1. d == 0 => dis = 0
     2. 当前气温值 < t => dis = d + 1
     3. 当前气温值 >= t => 再找下一个更大气温值
  3. 如果当前的气温值大于等于下一个气温值，记下一个更大气温值的索引为index，它的下一个更大气温值为t，则当前气温值到下一个更大气温值的距离dis等于：
     1. index不存在 => dis = 0
     2. 当前气温值 < t => dis = index - 当前索引值
     3. 当前气温值 >= t => 再找下一个更大气温值

代码

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] result = new int[T.length];
        result[T.length - 1] = 0;
        int[] next = new int[T.length];
        next[T.length - 1] = -1;
        int index;
        for (int i = T.length - 2; i >= 0; --i) {
            if (T[i] < T[i + 1]) {
                result[i] = 1;
                next[i] = i + 1;
            } else {
                index = next[i + 1];
                while (true) {
                    if (index == -1) {
                        result[i] = 0;
                        next[i] = -1;
                        break;
                    } else if (T[i] < T[index]) {
                        result[i] = index - i;
                        next[i] = index;
                        break;
                    } else {
                        index = next[index];
                    }
                }
            }
        }
        return result;
    }
}