[leetcode] 739. Daily Temperatures _ Algorithm Problem Solve for python

1. Problem

739. Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

2. Solution

I solved this problem like this.

Using stack, we can solve this problem.

• If stack is empty, append idx value and idx data.
• If stack top value is more smaller than now data, pop stack and confirm top and now data again.
• If stack top value isn’t smaller than now data, append now data on stack.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        output = [0] * len(temperatures)
        stack = [(temperatures[0], 0)]
        for idx, t in enumerate(temperatures):
            if idx == 0: 
                continue

            while stack:
                if stack[-1][0] < t:
                    top_val, top_idx = stack.pop()
                    output[top_idx] = idx - top_idx
                    if stack:
                        continue

                stack.append((t, idx))
                break
        
        return output