# LeetCode Medium 739. Daily Temperatures

tags: leetcode

問題

• Explore
• Problems

アイデア

｢毎日の気温の配列 T が与えられたとき､次にその日よりも温かい日が後何日で来るかを伝える配列を返せ｣という問題です｡こないならば　0 を代わりに返すようです｡

これは要素を1つずつ見て､それ以降の要素を見るという風に解こうとすると計算量が非常に大きくなります｡このようなときはそれらをスタックとして保管して､条件に合うものがあったら pop() して見ていくという風にやります｡

解法

• 気温の配列を最初から走査します｡
• この際に､既に通った要素の添字を保管するindicesというスタックを用意します｡
  • スタックに要素が入っていて､かつその添字が示す T の要素が走査中の要素よりも小さい時､ indices を pop() し､走査中の要素との差を格納します
• そして､現在の要素の添字をスタックに格納します｡

計算量

配列の大きさを N とします｡

• 時間計算量
  • $O(N)$
• 空間計算量
  • スタックの大きさに比例して $O(N)$

Python

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