【Java图解算法】739.每日温度

2023-12-22 06:23:51

单调栈

引言

生活中什么东西大的时候会变小,小的时候变大呢🐶?

答:当然是单调栈

739.每日温度

题目链接: https://leetcode.cn/problems/daily-temperatures/

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

思路

(暴力解法) O ( n 2 ) O(n^2) O(n2)

从左到右将温度遍历一遍,找到比当前温度更高的值之后更新

Java代码

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] result = new int[len];
        for(int i = 0; i < len; i ++ ) {
            int current = temperatures[i];
            for(int j = i + 1; j < len; j ++ ) {
                if(temperatures[j] > current) {
                    result[i] = j - i;
                    break;
                }
            }
        }
    return result;
    }
}

(单调栈) O ( n ) O(n) O(n)

求数组中比当前元素大的第一个数,最容易想到的就是用单调栈来解决这个问题

  • 单调栈里存放的元素是什么?

单调栈里只需要存放元素的下标i就可以了,如果需要使用对应的元素,直接T[i]就可以获取。

  • 单调栈里元素是递增呢? 还是递减呢?

大家可以记住这么一个结论:大减小增(从栈底到栈顶),求数组中比当前元素大的第一个数,就用递减栈,求数组中比当前元素小的第一个数,就用递增栈

接下来我们用temperatures = [73, 74, 75, 71, 71, 72, 76, 73]为例来逐步分析,定义一个result数组[0, 0, 0, 0, 0, 0, 0, 0], 最后输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

  1. 首先将第一个遍历的元素加入单调栈

  1. 加入T[1] = 74,因为T[1] > T[0](当前遍历的元素T[i]大于栈顶元素T[st.peek()]的情况)。
  2. 我们要保持一个递减栈(从栈底向上),所以将T[0]弹出,T[1]加入,此时result数组可以记录了,result[0] = 1,即T[0]右面第一个比T[0]大的元素是T[1]。

image-20230724175445976

我们从左到右遍历温度数组,对于每一个温度,我们将其下标入栈。如果当前温度比栈顶元素对应的温度高,说明栈顶元素的下一个更高温度就是当前温度,我们可以弹出栈顶元素,并将其下标对应的答案设置为当前下标减去栈顶元素下标。我们重复这个过程,直到栈为空或者当前温度小于等于栈顶元素对应的温度。最后,我们将当前温度的下标入栈,继续遍历下一个温度。

  1. 加入T[2],同理,T[1]弹出

image-20230724175539682

  1. 加入T[3],T[3] < T[2] (当前遍历的元素T[i]小于栈顶元素T[st.peek()]的情况),加T[3]加入单调栈。

image-20230724175843931

  1. 加入T[4],T[4] == T[3] (当前遍历的元素T[i]等于栈顶元素T[st.peek()]的情况),此时依然要加入栈,不用计算距离,因为我们要求的是右面第一个大于本元素的位置,而不是大于等于!

    大家可以发现 栈右边的那一列数 从栈底向上单调递减

image-20230724180034947

  1. 加入T[5],T[5] > T[4] (当前遍历的元素T[i]大于栈顶元素T[st.peek()]的情况),将T[4]弹出,同时计算距离,更新result

image-20230724180409062

  1. T[4]弹出之后, T[5] > T[3] (当前遍历的元素T[i]大于栈顶元素T[st.peek()]的情况),将T[3]继续弹出,同时计算距离,更新result

image-20230724180550787

  1. 直到发现T[5]小于T[st.peek()],终止弹出,将T[5]加入单调栈

image-20230724180855614

  1. 加入T[6],同理,需要将栈里的T[5],T[2]弹出

image-20230724181340222

image-20230724181409461

image-20230724181441988

  1. 加入T[7], T[7] < T[6] 直接入栈,这就是最后的情况,result数组也更新完了。

image-20230724181637336

这俩个元素不更新的话,result数组初始化的时候就是0,我们不需要更新result数组

在图解的时候我们遇见了三种情况

  • 情况一:当前遍历的元素T[i]小于栈顶元素T[st.peek()]的情况
  • 情况二:当前遍历的元素T[i]等于栈顶元素T[st.peek()]的情况
  • 情况三:当前遍历的元素T[i]大于栈顶元素T[st.peek()]的情况

Java代码

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
         int len = temperatures.length;
         int[] result = new int[len]; // 存放结果的数组

         Deque<Integer> stack = new LinkedList<>(); // 使用栈来保存未找到warmer day的下标
         stack.push(0); // 先将第一个温度的下标放入栈中
         for(int i = 1; i < len; i ++ ) { // 从第二个温度开始遍历
             while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                 // 如果栈非空且当前温度大于栈顶温度
                 result[stack.peek()] = i - stack.peek(); // 计算栈顶温度对应的下标到当前下标的距离,并赋值给结果数组
                 stack.pop(); // 弹出栈顶元素
             }
             stack.push(i); // 将当前下标压入栈中,等待找到warmer day的温度
         }
         return result; // 返回结果数组
    }
}

文章来源:https://blog.csdn.net/qq_52416556/article/details/135142640
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。