[leetcode - Bliend-150 ] 739. Daily Temperatures (Medium)

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.

给一个 array 纪录每日天气，如果明天的天气大于今天的天气则纪录 1，如果第四天的天气才大于今天的天气则纪录 3 (要经过 3 天才会变得比今天暖)。

Double For-Loop

最简单的解法可以用两个 for-loop 去遍历阵列，当 r > l 的时候将 r - l 的值放入 res

var dailyTemperatures = function(temperatures) {    const res = [];    for (let l = 0; l < temperatures.length; l++) {        let r = l + 1;        while (temperatures[r] <= temperatures[l] && r < temperatures.length) {           r++;        }        if (r < temperatures.length) res.push(r - l);        else res.push(0);    }    return res;};

虽然这样有办法解但他的 Time complexity 是 O(n^2)，再来找找有没有更好的方法。

Monotonic Stack

所谓的 Monotonic Stack 就是利用 stack 维护单纯递增或单纯递减的资料，用来找出下一个更大(或更小)的值，以这个题目为例 temperatures = [73,74,75,71,69,72,76,73]

从最后一项开始，因为 stack 为空的所以将 73 和他的 index 放入 stack 中，而因为是第一个所以 res 放入 0 代表没有比她更大的值。

移动 i 到 76 并将他和 stack 中最上面的值 (73) 比较，如果比较大则将 stack 中的值 pop 出来直到遇到比 76 大的值或 stack 清空。

这边将 73 pop 出来后 stack 清空了所以将 76 和他的 index 放入 stack 中，而因为是第一个所以 res 放入 0 代表没有比她更大的值。

移动 i 到 72 将他和 stack 中最上面的值 (76) 比较，72 比较小所以直接将它放入 stack 中并将他的 index 和 76 的 index 相减放入 res 中

移动 i 到 69 将他和 stack 中最上面的值 (72) 比较，69 比较小所以直接将它放入 stack 中并将他的 index 和 72 的 index 相减放入 res 中

移动 i 到 71 将他和 stack 中最上面的值 (69) 比较，将 stack 中的值 pop 出来直到遇到比 71 大的值或 stack 清空

这边将 69 pop 出去后 72 大于 71 于是停止 pop 并将 71 和他的 index 放入 stack 中，res 则放入 72 的 index 减去 71 的 index

诸如此类，移动 i 的时候将 i 的值与 stack 中最上面的值做比对，如果 stack 中的值小于 i 的值，则将 stack 的值 pop 出来直到大于 i 或是 stack 清空。

Coding

var dailyTemperatures = function(temperatures) {    const stack = [], res = [];    for (let i = temperatures.length - 1; i >= 0; i--) {        if (stack.length === 0) {            stack.push({ val: temperatures[i], index: i });            res[i] = 0;            continue;        }        if (stack[stack.length - 1].val > temperatures[i]) {            res[i] = stack[stack.length - 1].index - i;            stack.push({ val: temperatures[i], index: i });        } else {            while (stack[stack.length - 1]?.val <= temperatures[i]) {                stack.pop();            }            if (stack.length === 0) {                stack.push({ val: temperatures[i], index: i });                res[i] = 0;                continue;            }            res[i] = stack[stack.length - 1].index - i;            stack.push({ val: temperatures[i], index: i });        }    }    return res;};

Time complexity: O(n)

Reference