13ms Java solution with explanation


  • 1
    C
    public static int[] dailyTemperatures(int temperatures[]) {
    	int n = temperatures.length;
            if (n == 0)
                return temperatures;
    
    	// Values at an index are the number of days until a warmer temperature,
    	// for the corresponding temperature at temperatures[index].
    	int days[] = new int[n];
            
    	// Last day has no warmer days after it.
    	days[n - 1] = 0;
    
    	// For all days except last, iterate through starting at end of array.
    	// Won't run if n == 1, taken care of above.
    	int tempIndex;
    	for (int index = n - 2; index >= 0; index--) {
                
    	        // Check if the next day is warmer.
    		if (temperatures[index] < temperatures[index + 1]) {
    			days[index] = 1;
    			continue;
    		}
    
    		// If this code isn't continued over, then the next day is not warmer than the
    		// day at index, so therefore the next day that could possibly be warmer is at
    		// the day that is warmer than the next day.
    		tempIndex = index + 1 + days[index + 1];
    
    		/*
    		 * Move tempIndex to the index of the temperature that is the next warm day.
    		 * 
    		 * Loop runs while a warmer day hasn't been found, move tempIndex to the next
    		 * possible warmer day, based on property that the next possible warmer day is
    		 * at the next day's (given that the next day is not warmer than this day)
    		 * warmer day. If the next day does not have a warmer day (days[tempIndex] ==
    		 * 0), then this day cannot have a warmer day.
    		 * 
    		 * Problem: The loop exits when the next warmer day is found and when no options
    		 * are confirmed. Clarify this in assignment after the while loop by ensuring that 
    		 * the temperature at tempIndex is indeed warmer than the temperature at index.
    		 */
    		while (temperatures[index] >= temperatures[tempIndex] && days[tempIndex] > 0)
    			tempIndex += days[tempIndex]; // Move tempIndex to next possibly warmer day.
    
    		if (temperatures[index] < temperatures[tempIndex])
    			days[index] = tempIndex - index;
    		else
    			days[index] = 0;
    		}
    
    		return days;
    	}
    

Log in to reply
 

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