739. Daily Temperatures

LeetCode Problem Link (opens new window)

Given a list of daily temperatures temperatures, return a list such that, for each day in the input, it 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 a list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

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

Approach

The first approach to consider is the brute force method, using two nested for loops. This would search for the number of days one has to wait for a higher temperature. The time complexity of this approach is O(n^2).

Next, we'll consider using a monotonic stack.

You might wonder when to think of using a monotonic stack. When dealing with a one-dimensional array and needing to find the first element on the right (or left) that is larger or smaller than the current element, you should consider using a monotonic stack. This approach has a time complexity of O(n).

For this problem, we're essentially looking for an element's right-side first larger element, which suggests using a monotonic stack.

Concept of Monotonic Stack

Why is this effective? Why does it only require O(n) time complexity to find the first greater element on the right for every element?

The essence of the monotonic stack is trading space for time. As we traverse the array, we use a stack to record elements' indices, with the goal of finding the right-side first greater element for each element efficiently.

When employing a monotonic stack, consider the following points:

1. What element do we store in the monotonic stack?

   Only the index i of the element needs to be stored in the monotonic stack. Access the corresponding element directly with T[i].

2. Should the elements in the monotonic stack be increasing or decreasing?

   Note: In all discussions, "order" refers to the order from the stack head to the stack bottom. If we're seeking the first greater element on the right, use an increasing order (from head to bottom). Conversely, if seeking the first smaller element, use decreasing order.

Let's take temperatures = [73, 74, 75, 71, 71, 72, 76, 73] as an example to analyze the approach. The expected output is [1, 1, 4, 2, 1, 1, 0, 0].

Actions and Observations

Initialize with the first element in the stack.

Current temperatures is less than the stack top.

Current temperatures equals the stack top.

Current temperatures is greater than the stack top.

In detail, handle all three situations:

• Case 1: Current T[i] is less than T[st.top()]
• Case 2: Current T[i] is equal to T[st.top()]
• Case 3: Current T[i] is greater than T[st.top()]

C++ Code:

// Version 1
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> st;
        vector<int> result(T.size(), 0);
        st.push(0);
        for (int i = 1; i < T.size(); i++) {
            if (T[i] < T[st.top()]) {
                st.push(i);
            } else if (T[i] == T[st.top()]) {
                st.push(i);
            } else {
                while (!st.empty() && T[i] > T[st.top()]) {
                    result[st.top()] = i - st.top();
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

C Code:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {
    int len = temperaturesSize;
    *returnSize = len;

    int *result = (int *)malloc(sizeof(int) * len);
    memset(result, 0x00, sizeof(int) * len);

    int stack[len];
    memset(stack, 0x00, sizeof(stack));
    int top = 0;

    for (int i = 1; i < len; i++) {
        if (temperatures[i] <= temperatures[stack[top]]) {
            stack[++top] = i;
        } else {
            while (top >= 0 && temperatures[i] > temperatures[stack[top]]) {
                result[stack[top]] = i - stack[top];
                top--;
            }
            stack[++top] = i;
        }
    }
    return result;
}

Java Code:

class Solution {
  // Version 1
    public int[] dailyTemperatures(int[] temperatures) {

        int lens = temperatures.length;
        int []res = new int[lens];

        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for (int i = 1; i < lens; i++) {

            if (temperatures[i] <= temperatures[stack.peek()]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                    res[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
        }

        return res;
    }
}

Python Code:

Unoptimized Version

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0]*len(temperatures)
        stack = [0]
        for i in range(1, len(temperatures)):
            if temperatures[i] <= temperatures[stack[-1]]:
                stack.append(i)
            else:
                while len(stack) != 0 and temperatures[i] > temperatures[stack[-1]]:
                    answer[stack[-1]] = i - stack[-1]
                    stack.pop()
                stack.append(i)

        return answer

Optimized Version

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0]*len(temperatures)
        stack = []
        for i in range(len(temperatures)):
            while len(stack) > 0 and temperatures[i] > temperatures[stack[-1]]:
                answer[stack[-1]] = i - stack[-1]
                stack.pop()
            stack.append(i)
        return answer

Go Code:

Brute Force

func dailyTemperatures(t []int) []int {
    var res []int
    for i := 0; i < len(t)-1; i++ {
        j := i + 1
        for ; j < len(t); j++ {
            if t[j] > t[i] {
                res = append(res, j-i)
                break
            }
        }
        if j == len(t) {
            res = append(res, 0)
        }
    }
    return append(res, 0)
}

Monotonic Stack (Unoptimized Version)

func dailyTemperatures(temperatures []int) []int {
    res := make([]int, len(temperatures))
    stack := []int{0}

    for i := 1; i < len(temperatures); i++ {
        top := stack[len(stack)-1]
        if temperatures[i] < temperatures[top] {
            stack = append(stack, i)
        } else if temperatures[i] ==  temperatures[top] {
            stack = append(stack, i)
        } else {
            for len(stack) != 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
                res[top] = i - top
                stack = stack[:len(stack)-1]
                if len(stack) != 0 {
                    top = stack[len(stack)-1]
                }
            }
            stack = append(stack, i)
        }
    }
    return res
}

Monotonic Stack (Optimized Version)

func dailyTemperatures(num []int) []int {
    ans := make([]int, len(num))
    stack := []int{}
    for i, v := range num {
        for len(stack) != 0 && v > num[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]

            ans[top] = i - top
        }
        stack = append(stack, i)
    }
    return ans
}

JavaScript Code:

// Version 1
var dailyTemperatures = function(temperatures) {
    const n = temperatures.length;
    const res = Array(n).fill(0);
    const stack = [];
    stack.push(0);
    for (let i = 1; i < n; i++) {
        const top = stack[stack.length - 1];
        if (temperatures[i] < temperatures[top]) {
            stack.push(i);
        } else if (temperatures[i] === temperatures[top]) {
            stack.push(i);
        } else {
            while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
                const top = stack.pop();
                res[top] = i - top;
            }
            stack.push(i);
        }
    }
    return res;
};

// Version 2
var dailyTemperatures = function(temperatures) {
    const n = temperatures.length;
    const res = Array(n).fill(0);
    const stack = [];
    stack.push(0);
    for (let i = 1; i < n; i++) {
        while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const top = stack.pop();
            res[top] = i - top;
        }
        stack.push(i);
    }
    return res;
};

TypeScript Code:

function dailyTemperatures(temperatures: number[]): number[] {
    const length: number = temperatures.length;
    const stack: number[] = [];
    const resArr: number[] = new Array(length).fill(0);
    stack.push(0);
    for (let i = 1; i < length; i++) {
        let top = stack[stack.length - 1];
        while (
            stack.length > 0 &&
            temperatures[top] < temperatures[i]
        ) {
            resArr[top] = i - top;
            stack.pop();
            top = stack[stack.length - 1];
        }
        stack.push(i);
    }
    return resArr;
};

Rust Code:

impl Solution {
    pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
        let mut res = vec![0; temperatures.len()];
        let mut stack = vec![];
        for (idx, &value) in temperatures.iter().enumerate() {
            while !stack.is_empty() && temperatures[*stack.last().unwrap()] < value {
                let i = stack.pop().unwrap();
                res[i] = (idx - i) as i32;
            }
            stack.push(idx)
        }
        res
    }
}