Simple Java 11 ms (no stack)


  • 0
    D

    It is a variation of the brute-force method, but has much better performance by using information of previous results(in reverse order).

    Intuition
    Process each i in reverse order. For i, first compare it with i+1:
    If nums[i+1] > nums[i], then the result for i is 1;
    Else ( nums[i+1] <= nums[i]), then the next index we should compare is i+1+result[i+1], instead of i+2;

    public int[] dailyTemperatures(int[] nums) {
            if (nums == null || nums.length < 1) {
                return new int[0];
            }
            
            int n = nums.length;
            int[] result = new int[n];
            
            for(int i = n-2; i >= 0; i --) {
                int j = i + 1;
                while(true) {
                    if(nums[j] > nums[i]) {
                        result[i] = j - i;
                        break;
                    }
                    
                    if (result[j] == 0) {
                        break;
                    }
                    
                    j += result[j];
                }
            }
            
            return result;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.