LeetCode 739. Daily Temperatures (每日温度)

题目标签：HashMap

　　题目给了我们一组温度，让我们找出对于每一天，要等多少天，气温会变暖。返回一组等待的天数。

　　可以从最后一天的温度遍历起，从末端遍历到开头，对于每一天的温度，把它在T里面的index存入 temp[101] 保存。然后对于每一天的温度，从温度+1 到100 全部遍历后，找出变暖温度里离当天最近的那一天。存入answer。具体看code。

Java Solution:

Runtime: 8 ms, faster than 91.33%

Memory Usage: 42.7 MB, less than 93.43%

完成日期：04/02/2019

关键点：从结尾开始遍历到开头。

class Solution {

    public int[] dailyTemperatures(int[] T) {

        int[] answer = new int[T.length];

        int[] temp = new int[101];

        Arrays.fill(temp, Integer.MAX_VALUE);

        for(int i = T.length - 1; i >= 0; i--) // iterate from end to start

        {

            int warmer_index = Integer.MAX_VALUE;

            for(int t = T[i] + 1; t <= 100; t++) // for this day, find the closest warmer day

            {

                if(temp[t] < warmer_index)

                    warmer_index = temp[t];

            }

            if(warmer_index < Integer.MAX_VALUE)

                answer[i] = warmer_index - i;

            // store current day's temp into temp array

            temp[T[i]] = i;

        }

        return answer;

    }

}

参考资料：https://leetcode.com/problems/daily-temperatures/discuss/?currentPage=1&orderBy=recent_activity&query=

LeetCode 题目列表 - LeetCode Questions List

题目来源：https://leetcode.com/

巴特西

LeetCode 739. Daily Temperatures (每日温度)

最新文章

热门文章