LeetCode-7039:Daily Temperature(毎日の温度)

Given a list of daily temperature T,return a list such that,for each day in the in put,tells You how many days ou would have to wait until a warmer temperature.If there isのfuture day for which is.put.put.
For example、given the list of temperature T=[73,74,75,71,69,72,76,73]、your out put shound be[1,4,2,1,1,0,0]
Note:The length of temperature s will be in the range[1,30000].Each temperature will be an integer in the range[30,100]
考え方
単調なスタックを使って解決します.
Java実現

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int length = T.length;
        Deque<Integer> stack = new ArrayDeque<>(length);
        int[] results = new int[length];
        for (int i = 0; i < length; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int t = stack.poll();
                results[t] = i - t;
            }
            stack.push(i);
        }
        return results;
    }
}

Python実現

from typing import List, Tuple, Dict

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

Scala実装

import scala.collection.mutable.Stack

object Solution {
    def dailyTemperatures(T: Array[Int]): Array[Int] = {
        val length = T.length
        val stack = new Stack[Int]()
        val results = new Array[Int](length)
        for (i <- 0 until length) {
            while (!stack.isEmpty && T(i) > T(stack.top)) {
                val t = stack.pop()
                results(t) = i - t;
            }
            stack.push(i)
        }
        results
    }
}