739. Daily Temperatures

• 특정 날짜 구간의 일별 온도가 주어졌을 때 각 날짜 열 온도로 부터 처음으로 더 높은 온도가 등장하는 날 까지 몇일이 걸리는지 구하는 문제이다.
• 예를 들어 [25, 23, 27, 21]의 경우 25 → 27까지 2일, 23 → 27까지 1일, 27의 경우 이후 더 온도가 높은 날이 없고, 21은 마지막 날이므로 결과는 [2, 1, 0, 0]이 된다.

• 너무 어렵게 생각해서 못 풀었는데 힌트를 보니까 갑자기 생각이 났다.
• 배열을 정방향으로 순회해서 풀려고 하니 어려웠던 것 같다.

• 이 문제는 특정 일자를 기준으로 해당 일자 이후에 자신보다 온도가 높은 날 중 가장 가까운 날을 찾으면 되는 문제이다.
• 온도의 범위가 30 ~ 100이므로 배열을 만들어서 각 온도가 등장한 날을 배열 indices 에 기록할 수 있다.
• 특정일 이후에 각 온도별로 가장 근접한 날을 기록해야 하므로 온도 temperature 배열을 역순으로 순회하며 기록하면 된다.
• 각 온도가 등장한 날을 기록한 배열 indices 을 순회하면서 현재 온도 보다 높은 온도 중 가장 근접한 날을 찾는다.

class Solution {
    final int MIN_TEMP = 30;
    final int MAX_TEMP = 100;

    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        int[] indices = new int[MAX_TEMP - MIN_TEMP + 1];
        for (int i = n - 1; i >= 0; --i) {
            int t = temperatures[i];
            indices[t - MIN_TEMP] = i;
            int nextIndex = Integer.MAX_VALUE;
            for (int j = t + 1; j <= MAX_TEMP; ++j) {
                if (indices[j - MIN_TEMP] == 0) continue;
                nextIndex = Math.min(nextIndex, indices[j - MIN_TEMP]);
            }
            if (nextIndex != Integer.MAX_VALUE) {
                result[i] = nextIndex - i;
            }
        }
        return result;
    }
}