夯实算法-每日温度

敞开生长之旅！这是我参加「日新计划 12 月更文应战」的第9天，点击检查活动概况

标题：LeetCode

给定一个整数数组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]

提示：

• 1<=temperatures.length<=1051 <=temperatures.length <= 10^51<=temperatures.length<=105
• 30 <=temperatures[i]<= 100

解题思路

依据题意便是关于某一元素[i]，要在[i+1, n-1]里边找j，使[j] > [i]，要找第一个[j]，假如没有便是0。

要提高功率，基本上遍历一次，将已遍历过的元素需求放入一个容器中，每次遍历时将当时元素与容器中的元素。标题要求是找最少的天数，因此应该与最近的元素进行比较，也即“后入先出”，可以用栈。

先将当时元素入栈，当遍历到后面的元素时，与栈顶的元素比较，假如元素大于栈顶元素，说明栈顶元素找到了成果，这个元素与栈顶之间的距离便是栈顶元素需求的天数。栈中的数据是数组下标。

栈中保存的是还没有找到成果的元素，也即较高的温度，遍历到当时元素[i]时，先与栈顶下标比较，假如[i]>[highTemps.peek()]，那么栈顶这天就找到了成果，可以出栈了，要继续比较，直到栈里温度都大于[i]或者栈空了为止。

因为当时元素[i]，必定找不到成果，所以当时i是必定要入栈的。

几个关键：

• 栈里数据是下标，以方便计算天数，天数其实便是数组下标之差
• 栈里保存的元素是较高的温度，也便是还没有找到成果的某几天
• 当时元素必定要入栈的
• 当时元素与栈中元素进行比较，以找到栈中元素的成果（需求的天数）。

代码完成

public int[] dailyTemperatures(int[] temperatures) {
    int[] result = new int[temperatures.length];
    Stack < Integer > highTemps = new Stack <>();
    for (int i = 0; i < temperatures.length; i++) {
        while (!highTemps.isEmpty() && temperatures[i] > temperatures[highTemps.peek()]) {
            int prev = highTemps.pop();
            result[prev] = i - prev;
        }
        highTemps.push(i);
    }
    return result;
}

复杂度剖析

• 空间复杂度：$O(1)$
• 时间复杂度：$O(n)$

在(JUEJIN)一同分享知识, Keep Learning!