_739. Daily Temperatures.md

739. Daily Temperatures

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 13, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Stack, Monotonic Stack

Acceptance Rate : 66.159 %

---

Solutions

• m739 v2 MUCH faster.java
• m739.java
• m739 v2.c
• m739.py

Java

m739 v2 MUCH faster.java

// Saw this solution and tried it myself and oh my is it elegant. Beautiful solution.

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] output = new int[temperatures.length];

        int currentMax = 0;
        for (int i = temperatures.length - 1; i >= 0; i--) {
            if (temperatures[i] >= currentMax) {    // default 0
                currentMax = temperatures[i];
                continue;
            }

            int offset = 1;
            while (temperatures[i] >= temperatures[i + offset]) {
                offset += output[i + offset];
            }
            output[i] = offset;
        }

        return output;
    }
}

m739.java

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<int[]> previousMaxes = new Stack<>();  // Schema (temp, indx)

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

        for (int i = temperatures.length - 1; i >= 0; i--) {
            while (!previousMaxes.isEmpty()) {
                if (previousMaxes.peek()[0] > temperatures[i]) {
                    output[i] = previousMaxes.peek()[1] - i;
                    break;
                }
                previousMaxes.pop();
            }
            previousMaxes.push(new int[] {temperatures[i], i});
        }

        return output;
    }
}

C

m739 v2.c

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

    for (int i = temperaturesSize - 1; i >= 0; i--) {
        if (temperatures[i] >= currentMaxTemp) {
            currentMaxTemp = temperatures[i];
            output[i] = 0;
            continue;
        }

        int offset = 1;
        while (temperatures[i] >= temperatures[i + offset]) {
            offset += output[i + offset];
        }

        output[i] = offset;
    }

    return output;
}

Python

m739.py

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        output = [0] * len(temperatures)
        tempStack = []                      # schema: (temperature, index)

        for i in range(len(temperatures) - 1, -1, -1) :
            while tempStack :
                if tempStack[-1][0] > temperatures[i] :
                    output[i] = tempStack[-1][1] - i
                    break
                else :
                    tempStack.pop()
            
            tempStack.append((temperatures[i], i))

        return output