LeetCode 739 - Daily Temperatures

https://leetcode.com/problems/daily-temperatures/description/

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

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

    public int[] dailyTemperatures(int[] T) {

        int[] ans = new int[T.length];

        Stack<Integer> stack = new Stack();

        for (int i = T.length - 1; i >= 0; --i) {

            while (!stack.isEmpty() && T[i] >= T[stack.peek()]) stack.pop();

            ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;

            stack.push(i);

        }

        return ans;

    }

https://leetcode.com/problems/daily-temperatures/discuss/109832/Java-Easy-AC-Solution-with-Stack

public int[] dailyTemperatures(int[] temperatures) {
    Stack<Integer> stack = new Stack<>();
    int[] ret = new int[temperatures.length];
    for(int i = 0; i < temperatures.length; i++) {
        while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            ret[idx] = i - idx;
        }
        stack.push(i);
    }
    return ret;
}

public int[] dailyTemperatures(int[] temperatures) {
    int[] stack = new int[temperatures.length];
    int top = -1;
    int[] ret = new int[temperatures.length];
    for(int i = 0; i < temperatures.length; i++) {
        while(top > -1 && temperatures[i] > temperatures[stack[top]]) {
            int idx = stack[top--];
            ret[idx] = i - idx;
        }
        stack[++top] = i;
    }
    return ret;
}

public int[] dailyTemperatures(int[] temperatures) {

if (temperatures == null) {

return new int[] {};

}

int[] result = new int[temperatures.length];

Deque<Integer> stack = new ArrayDeque<>();

// 1,2,3

for (int i = 0; i < temperatures.length; i++) {

while (!stack.isEmpty()) {

if (temperatures[i] <= temperatures[stack.peekLast()]) {

break;

}

result[stack.peekLast()] = i - stack.peekLast(); //

stack.pollLast();

}

stack.addLast(i);

}

// 3,2,1

// while(!stack.isEmpty()) {

// result[stack.peekLast()] = 0;

// stack.pollLast();

// }

// no need

// for (Integer i : stack) {

// result[i] = 0;

// }

return result;

}

X.

The problem statement asks us to find the next occurrence of a warmer temperature. Because temperatures can only be in [30, 100], if the temperature right now is say, T[i] = 50, we only need to check for the next occurrence of 51, 52, ..., 100 and take the one that occurs soonest.

Algorithm

Let's process each i in reverse (decreasing order). At each T[i], to know when the next occurrence of say, temperature 100 is, we should just remember the last one we've seen, next[100].

Then, the first occurrence of a warmer value occurs at warmer_index, the minimum of next[T[i]+1], next[T[i]+2], ..., next[100].

• Time Complexity: $O(NW)$, where $N$ is the length of T and $W$ is the number of allowed values for T[i]. Since $W = 71$, we can consider this complexity $O(N)$.
• Space Complexity: $O(N + W)$, the size of the answer and the next array.

    public int[] dailyTemperatures(int[] T) {
        int[] ans = new int[T.length];
        int[] next = new int[101];
        Arrays.fill(next, Integer.MAX_VALUE);
        for (int i = T.length - 1; i >= 0; --i) {
            int warmer_index = Integer.MAX_VALUE;
            for (int t = T[i] + 1; t <= 100; ++t) {
                if (next[t] < warmer_index)
                    warmer_index = next[t];
            }
            if (warmer_index < Integer.MAX_VALUE)
                ans[i] = warmer_index - i;
            next[T[i]] = i;
        }
        return ans;
    }