739. Daily Temperatures

Description of Problem

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

Solution

Tags: Monotonic Stack

The best problem about Monotonic Stack for beginners.

Explanation

Solve the problem by monotonic stack where the top of the stack is the smallest element in the stack: Loop over the array reversely; before insertion of the current element, remove all elements that less than or equal to the current elements from the top.

Since we need to calculate the distance of current element and next greater element (NGE), the stack stores index instead of value of an element.

For convinence of proof, assume our monotonic stack stores (index, value) tuples.

Loop invariant: The value of the top of the stack is the smallest value in the stack AND it is greater than the current element

• Initialisation: Stack is empty, thus it is vacuously true.
• Maintenance: Suppose the invariant is true before an iteration. Now consider the current element before insertion:
  1. The algorithm removes all elements where their value are less than or equal to the value of current element.
  2. After all, the stack contains only elements where their value greater than the value of the current element. The value of the top of the stack is still the smallest value among the values in the stack.
  3. Thus, the loop invariant preserves. The algorithm insert the current element.
• Termination: The loop invariant is true at the termination.

Example

• If we want to insert 75, we have to remove 69 and 72.
• If we want ot insert 71, we have to remove 69.
• If we want ot insert 50, we don't need to remove any element.

Code (Rust)

impl Solution {
    pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
        let mut mono_stack = Vec::new();
        let n = temperatures.len();
        let mut ans = vec![0; n];
        for i in (0..n).rev() {
            while let Some(&j) = mono_stack.last() {
                if temperatures[i] >= temperatures[j] {
                    mono_stack.pop();
                }else{
                    break;
                }
            }
            if let Some(&j) = mono_stack.last() {
                ans[i] = (j - i) as i32;
            }else {
                ans[i] = 0;
            }
            mono_stack.push(i);
        }

        return ans;
    }
}

Complexity

• \(n\) is length of temperatures

Time Complexity

• \(S(n) = \Theta(2n) = \Theta(n)\)
  • Iterate temperatures
  • Pop at most \(n\) elements

Auxiliary Space

• \(S(n) = O(n)\)
  • Store at most \(n\) elements