739. Daily Temperatures

Option 1: stack T = O(n) where n = len(T)

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        stack = []
        res = [0] * len(T)
        for i, temp in enumerate(T):
            while stack and stack[-1][0] < temp:
                _, idx = stack.pop()
                res[idx] = i - idx
            stack.append([temp, i])
        return res

Option 2

scan from right to left. maintain an array to record the index of temperature. nextTemp[i] = j means j is the min index found so fat with temperature
update nextTemp[i] while scanning
nextIdx = min(nextTemp[cur+1:]): check all temperatures that are warmer, get the min index

T = O(C * N) where C = len(nextTemp) is constant and N = len(T).

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        n = len(T)
        nextTemp = [n] * 102 # nextTemp[i] = j so j is the min index of temp i
        res = [0] * n
        for i in range(n-1, -1, -1):
            cur = T[i]
            nextIdx = min(nextTemp[cur+1:])
            res[i] = nextIdx - i if (nextIdx != n) else 0
            nextTemp[cur] = i
        return res

739. Daily Temperatures - cocoder39/coco39_LC GitHub Wiki