[!info] related notes 算法面试题型 MOC 单调栈

每日温度

题目

739. 每日温度 - 力扣（LeetCode）

题解

• 单调栈

从右往左遍历，栈中存下标而非温度。压入当前下标前，弹出温度小于或等于当前温度的候选；相等不算升温。剩余栈顶是右侧最近的更高温度，下标差就是等待天数；没有候选时为 0。

var dailyTemperatures = function(temperatures) {
    const n = temperatures.length;
    const ans = Array(n).fill(0);
    const st = [];
    for (let i = n-1;i>=0;i--) {
        const t = temperatures[i];
        while(st.length && t >= temperatures[st[st.length-1]]) {
            st.pop();
        }
        if (st.length) {
            ans[i] = st[st.length - 1] - i;
        }
        st.push(i);
    }
    return ans;
};