739.daily-temperatures.md

739. Daily Temperatures

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

Brute Force

fun dailyTemperatures(temperatures: IntArray): IntArray {
    val results = IntArray(temperatures.size) 
    for (i in 0 until temperatures.size) {
        var day = 0
        var findWarnerDay = false
        for (j in i + 1 until temperatures.size) {
            day++
            if (temperatures[j] > temperatures[i]) {
                findWarnerDay = true
                break
            }
        }

        results[i] = if (findWarnerDay) day else 0
    }
    return results
}

Monotonic Stack

When using monotonic stack, we can reduce the time complexity down to O(n).

• We push the day index into stack if the temperature is colder than previous day.
• We pop all day index if current the warner, and update the result.

fun dailyTemperatures(temperatures: IntArray): IntArray {
    val results = IntArray(temperatures.size)
    // We use day as item
    val monotonicStack = Stack<Int>()
    for (day in 0 until temperatures.size) {
        // Pop all item violating monotonic property
        while (!monotonicStack.isEmpty() && temperatures[monotonicStack.peek()] < temperatures[day]) {
            val previousDay = monotonicStack.pop()
            results[previousDay] = day - previousDay
        }
        monotonicStack.push(day)
    }
    while (!monotonicStack.isEmpty()) {
        results[monotonicStack.pop()] = 0
    }
    return results
}