Daily Temperatures

1. Problem Description

Given a list of daily temperatures, generate a new list where each position contains the minimum number of days you must wait to observe a warmer temperature. If the temperature never rises afterward, put 0 at that position.

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

2. Approach

1. Approach 1
   • Brute force
   • Use two nested loops to find the first later value greater than the current value

3. Implementation

3.1. Brute Force

package main

func dailyTemperatures(T []int) []int {
	res := make([]int, 0)

	for i := 0; i < len(T); i++ {
		minJ := i
		for j := i + 1; j < len(T); j++ {
			if T[j] > T[i] {
				minJ = j
				break
			}
		}
		res = append(res, minJ-i)
	}

	return res
}

3.2. Monotonic Stack

func dailyTemperatures(temperatures []int) []int {
    res := make([]int, len(temperatures))
    var stack []int// Monotonic stack storing indices of decreasing values
    for i, num := range temperatures {
        // Maintain the monotonic-stack property while producing results
        for !empty(stack) && num > temperatures[top(stack)] {
            prevIndex := top(stack)
            stack = pop(stack)
            res[prevIndex] = i-prevIndex
        }
        stack = push(stack, i)
    
    }
    return res
}

func empty(stack []int) bool {
    return len(stack) == 0
}

func push(stack []int, i int) []int {
    stack = append(stack, i)
    return stack
}

func top(stack []int) int {
    return stack[len(stack)-1]
}

func pop(stack []int) []int {
    return stack[:len(stack)-1]
}

4. References

• Daily Temperatures - LeetCode
• LeetCode Illustrated | 739. Daily Temperatures - LeetCode