LeetCode-739. 每日温度

题目来源

739. 每日温度

题目详情

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 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 <= 105
• 30 <= temperatures[i] <= 100

题解分析

解法一：暴力

1. 暴力法就比较容易想到了，就是针对每个温度值 向后进行依次搜索 ，找到比当前温度更高的值，这是最容易想到的办法。
2. 其原理是从左到右除了最后一个数其他所有的数都遍历一次，最后一个数据对应的结果肯定是 0，就不需要计算。
3. 遍历的时候，每个数都去向后数，直到找到比它大的数，数的次数就是对应输出的值。
4. 这种方法比较暴力，这里就不贴代码了，读者可以自己去尝试，应该是很容易的。

解法二：单调栈

1. 这道题目是典型的单调栈的使用方法，这个栈有点特殊，它是递减栈：即栈里只有递减元素。
2. 具体操作如下：
   • 遍历整个数组，如果栈不空，且当前数字大于栈顶元素，那么如果直接入栈的话就不是 递减栈 ，所以需要取出栈顶元素，由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，直接求出下标差就是二者的距离。
   • 继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来。
3. java代码实现

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        Deque sta = new LinkedList<>();

        for(int i = 0; i temperatures[sta.peekFirst()]){
                int curt = sta.pollFirst();
                res[curt] = i - curt;
            }
            sta.addFirst(i);
        }
        while(!sta.isEmpty()){
            int curt = sta.pollFirst();
            res[curt] = 0;
        }
        return res;
    }
}

结果展示

相似题

以下列出了单调栈的问题，供大家参考。