[leetcode] 739. Daily Temperatures

문제

739. Daily Temperatures

비슷한 문제

• programmers 42584.주식 가격
• 접근 방식이 완전 같아서 함께 풀어보면 좋다!

분석

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

• temperature의 length가 $10^5$ 가 될 수 있으므로, 시간복잡도 $O(n^2)$으로 풀면 안됌 (완전탐색 NO!)

• 해당 문제는, temperature가 "일정 조건" (본인의 temperature보다 높은 temperature)을 만났을 때만 반응한다!

• Valid Parentheses 문제와 비슷한 조건 --> Stack으로 풀어보쟈!

첫 코드 작성

class Solution:
    def dailyTemperatures(self, temperatures):
        temps = deque()
        n = len(temperatures)
        answers = [0] * n
        temps.append(0)
        for cur_i in range(1, n):
            if len(temps)==0:
                continue
            else:
                while temps:
                    temp_idx = temps[-1]
                    #print("t, idx: ", t, idx)
                    # if temperature is warmer
                    if (temperatures[cur_i] - temperatures[temp_idx]) > 0:
                        temps.pop()
                        # update answers
                        answers[temp_idx] = cur_i - temp_idx
                    else:
                        break
                
                temps.append((cur_i))
                
        return answers

결과

2번째 코드 (Fine tuned)

• 필요없는 조건 없애고, while문에 들어가는 조건 (temperatures[temps[-1]] < temperatures[cur_i])을 처음부터 명시하여 줌

class Solution:
    def dailyTemperatures(self, temperatures):
        temps = deque()
        n = len(temperatures)
        answers = [0] * n
        temps.append(0)
        for cur_i in range(1, n):
            while temps and (temperatures[temps[-1]] < temperatures[cur_i]):
                temp_idx = temps.pop()
                answers[temp_idx] = cur_i - temp_idx
                
            temps.append((cur_i))
                
        return answers

결과