LeetCode Entry
739. Daily Temperatures
Array of distances to the next largest.
739. Daily Temperatures medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/489
Problem TLDR
Array of distances to the next largest.
Intuition
Let’s walk array backwards and observe which numbers we need to keep track of and which are irrelevant:
0 1 2 3 4 5 6 7
73 74 75 71 69 72 76 73
73 73 7
76 76 6
72 76 72 6 5 6 - 5 = 1
69 76 72 69 6 5 4
71 76 72 71 6 5 3 5 - 3 = 2
As we see, we must keep the increasing orders of values and drop each less than current. This technique is a known pattern called Monotonic Stack.
Approach
There are several ways to write that, let’s try to be brief.
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun dailyTemperatures(temps: IntArray): IntArray =
Stack<Int>().run {
temps.indices.reversed().map { i ->
while (size > 0 && temps[peek()] <= temps[i]) pop()
(if (size > 0) peek() - i else 0).also { push(i) }
}.reversed().toIntArray()
}
pub fn daily_temperatures(temps: Vec<i32>) -> Vec<i32> {
let (mut r, mut s) = (vec![0; temps.len()], vec![]);
for (i, &t) in temps.iter().enumerate().rev() {
while s.last().map_or(false, |&j| temps[j] <= t) { s.pop(); }
r[i] = (*s.last().unwrap_or(&i) - i) as i32;
s.push(i);
}
r
}