1D list

739. Daily Temperatures

Naive O(n²) solution will get TLE.

Here is an improved version by using bisect after collecting all the indexes of temperatures.

36 / 37 test cases passed. TLE
class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        temp_idx = collections.defaultdict(list)
        for i, t in enumerate(T):
            temp_idx[t].append(i)
        res = []
        for i, t in enumerate(T):
            this_res = []
            for key in range(t+1, 101):
                j = bisect.bisect_right(temp_idx[key], i)
                if j<len(temp_idx[key]):
                    this_res.append(temp_idx[key][j])
            if this_res:res.append(min(this_res)-i)
            else:res.append(0)
        return res

Change the loose 101 bound the maxT+1, it works. The complexity of this algorithm is O(n*k log n)

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        temp_idx = collections.defaultdict(list)
        MAXT = 0
        for i, t in enumerate(T):
            MAXT = max(MAXT, t)
            temp_idx[t].append(i)
        res = []
        for i, t in enumerate(T):
            this_res = []
            for key in range(t+1, MAXT+1):
                j = bisect.bisect_right(temp_idx[key], i)
                if j<len(temp_idx[key]):
                    this_res.append(temp_idx[key][j])
            if this_res:res.append(min(this_res)-i)
            else:res.append(0)
        return res

A better one (the idea is similar to the monotonically queue)

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