739. Daily Temperatures

Problem

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Problem Summary

Given an array of temperatures, output how many days in the future a higher temperature than the current day's temperature will occur. For example, a temperature higher than 73 degrees appears on the 1st future day, and a temperature higher than 75 degrees appears on the 4th future day.

Solution Approach

This problem can be handled normally according to the problem statement, using two nested loops. Another approach is to use a monotonic stack; just maintain a monotonically decreasing stack.

Code

package leetcode

// Solution 1: brute-force approach
func dailyTemperatures(T []int) []int {
	res, j := make([]int, len(T)), 0
	for i := 0; i < len(T); i++ {
		for j = i + 1; j < len(T); j++ {
			if T[j] > T[i] {
				res[i] = j - i
				break
			}
		}
	}
	return res
}

// Solution 2: monotonic stack
func dailyTemperatures1(T []int) []int {
	res := make([]int, len(T))
	var toCheck []int
	for i, t := range T {
		for len(toCheck) > 0 && T[toCheck[len(toCheck)-1]] < t {
			idx := toCheck[len(toCheck)-1]
			res[idx] = i - idx
			toCheck = toCheck[:len(toCheck)-1]
		}
		toCheck = append(toCheck, i)
	}
	return res
}