[Neetcode/Stack] Daily Temperatures

https://neetcode.io/problems/daily-temperatures?list=neetcode150

NeetCode

Approach 1 -> nest loop (time complexity: O(n^2))

 

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = []
        
        # t = temperature[i]
        for i, t in enumerate(temperatures):
            j = i+1

            while j < len(temperatures) and temperatures[i] >= temperatures[j]:
                j+=1
            
            if j == len(temperatures):
                res.append(0)
            else:
                res.append(j-i)

 

Approach 2 -> stack (monotonically decreasing order)

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:        
        res = [0] * len(temperatures)
        
        stack = []

        for i, t in enumerate(temperatures):
            while stack and stack[-1][1] < t:
                pop_i, pop_t = stack.pop()
                res[pop_i] = i - pop_i
            
            stack.append((i, t))
            print(stack)

        return res

• for i, t in enumerate(temperatures):
  • i -> index
  • t -> temperature's element
• stack[-1][1]
  • ex) stack = [(0, 73), (1, 74), (2, 75)]
    • stack[1] → (1, 74)
    • stack[1][-1] → 74 (the last item of the tuple)