Leetcode 739. Daily Temperatures-JavaScript


Daily Temperatures - https://leetcode.com/problems/daily-temperatures/

1.問題の説明


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.
数値因子からなる温度アレイが与えられると、iの2番目の温度は、より暖かい温度因子を得るのに数日かかるという問題がある.すなわち,現在与えられている温度は数日後により高い温度に達することができ,これは配列で表される問題である.並びが終わる前にもっと暖かい日に出会わなかったら0を返します.

2.解答


Nは最大10^5なので、毎日の温度は他の日付の温度とは比べものにならない.例:
for (let i=0; i<N; i++) {
	for (let j=i+1; j < N; j++) {
      if (temperature[i] < temperature[j])
        ....
}
このように構成すると,時間効率は高くない.だからスタックを使いました.
すべての値は(온도, 날짜)の形でstackにプッシュされます.stackに値が含まれ、現在の温度がstackの最後のインデックスの温度より高い場合、popは値を入力します.繰り返し実行します.そうしないと中断します.stackは常に昇順に格納されるため、現在の温度よりも高いstack値に遭遇した場合、重複文を返す理由はありません.
retコードの例を見てみましょう.temperatures = [73,74,75,71,69,72,76,73]
  • の最初の価格は73です.そしてstack=[73]
  • stackの最後の値は現在の値より小さいです.popとスタック.stack = [74]
  • stackの最後の値は現在の値より小さいです.popとスタック.stack = [75]
  • スタックの最後の値は現在の値より大きい.山積みだけ.stack = [75, 71]
  • スタックの最後の値は現在の値より大きい.山積みだけ.stack = [75, 71, 69]
  • stackの最後の値は現在の値より小さいです.popとスタックを繰り返します.stack = [75, 72]
  • を繰り返します
  • 3.正解コード

    const dailyTemperatures = (temperatures) => {
      	// 배열 초기화
        const answer = Array.from({length: temperatures.length}, () => 0);
        const stack = [];
        temperatures.forEach((temperature, day) => {
          	// stack의 값이 들어있고, 현재온도가 stack의 마지막 온도보다 클 때, pop하고 정답입력.
            while (stack.length && temperature > stack[stack.length-1][0]) {
                const [__, prevDay] = stack.pop();
                answer[prevDay] = day - prevDay;
            }
            
            stack.push([temperature, day]);
        })
        return answer;
    };