经典算法题 - 每日温度

前言

经济萧条导致了移动端开发岗的锐减，当前环境下研发人员的竞争尤其激烈。算法，成为了面试大厂的必备条件。

知识点

• 单调栈

描述

• 给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。
• 如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例1

• 输入: temperatures = [73,74,75,71,69,72,76,73]
• 输出：[1,1,4,2,1,1,0,0]

示例2

• 输入: temperatures = [30,40,50,60]
• 输出: [1,1,1,0]

示例3

• 输入: temperatures = [30,60,90]
• 输出: [1,1,0]

思路

• 这题可以用暴力破解法求解，也是我第一时间的解法，虽然能 AC，但效果不佳。
• 标准的解法是使用单调栈求解，比较新颖。

代码1，暴力法

function dailyTemperatures(arr) {
    let res = [];
    for (let i = 0; i < arr.length; i++) {
        res.push(findNext(arr, i));
    }
    return res;
}

/**
 * 暴力法，直接从当前元素后边找到第一个大于它的位置
 * 找不到则为0
 */
function findNext(arr, index) {
    if (index >= arr.length - 1) {
        return 0;
    }
    for (let i = index + 1; i < arr.length; i++) {
        if (arr[index] < arr[i]) {
            return i - index;
        }
    }
    return 0;
}

代码2，单调栈

• 单调栈的基本思路是维护一个单调递增或单调递减的栈，由于题目只要下标，栈中保存下标即可
• 在遍历输入数组的过程中进行判断：
• 如果栈为空则入栈
• 如果当前元素小于或等于栈顶元素，意味着在降温，入栈
• 如果当前元素大于栈顶元素，意味着最少找到了一个升温的位置，更新返回的数组下标
• 如果遍历完了栈中仍有元素，则将栈中的元素对应的下标赋值为0

/**
 * 单调栈解法：
 * 维护一个单调递减的栈，遍历原数组，对其值则进行比较，
 * 如果栈为空，则直接入栈
 * 如果栈顶元素较大，也直接入栈
 * 如果栈顶元素较小，意味着新的元素为之前元素的一个升值，取出栈中元素并更新其差值
 * 如果原数据遍历完后栈仍有元素，则栈中元素对应位置找不到升值的点，对应的差值为0
 */
function solution(arr) {
    // 创建同样长度的结果数组
    let res = new Array(arr.length);
    // 创建单调栈
    let stack = [];
    // 遍历数组元素
    for (let i = 0; i < arr.length; i++) {
        // 如果单调栈为空则入栈
        if (stack.length === 0) {
            stack.push(i);
            continue;
        }
        // 循环读栈
        while (stack.length > 0) {
            // 拿到栈顶元素
            let index = stack[stack.length - 1];
            // 如果当前元素比栈顶还小，则要入栈
            if (arr[i] <= arr[index]) break;
            // 如果当前元素比栈顶的大，即找到了一个升温的位置，更新栈顶元素的位置的值为两者差值
            res[index] = i - index;
            // 更新一个去掉一个元素
            stack.pop();
        }
        // 操作完后，将当前元素入栈，备用
        stack.push(i);
    }
    // 所有元素遍历完了，如果栈中还有元素，栈中肯定是降序排列，并且都没有升温的可能了，其值要更新为0
    while (stack.length > 0) {
        let index = stack.pop();
        res[index] = 0;
    }
    return res;
}

总结

• 升温数组这题其实主要考查对单调栈的运用
• 对栈的运用得当，则很好解