Leetcode-每日温度Java

秒速五厘米 2023-01-03 06:12 190阅读 0赞

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = \[73, 74, 75, 71, 69, 72, 76, 73\]，你的输出应该是 \[1, 1, 4, 2, 1, 1, 0, 0\]。

提示：气温 列表长度的范围是 \[1, 30000\]。每个气温的值的均为华氏度，都是在 \[30, 100\] 范围内的整数。

解法一、暴力破解

对于每一个温度，向后进行查询，如果遇到温度比自己高，则直接计算索引并终止计算，后续的值不需要进行计算。

如：对于Index = 0 的第一个温度73，向后进行查询，找到 index = 1 的温度比自己高，则直接计算索引并终止，后续不管 index = 2 的75比自己温度高也不需要进行关注了。代码如下

private static int[] dailyTemperatures1(int[] T) {
            int length = T.length;
            int[] result = new int[length];
    
            for (int i = 0; i < length; ++i) {
                for (int j = i + 1; j < length; ++j) {
                    //从前像后遍历，找到一个比自身大的温度，就不需要继续往后找了
                    if (T[j] > T[i]) {
                        result[i] = j - i;
                        break;
                    }
                }
            }
            return result;
        }

暴力破解的时间复杂度是很高的，很多值被遍历了无数次，如何减少遍历次数？

解法二、如下图所示，如果当前需要计算i指向的后续第一个比75大的温度，我们不需要一步一步的往后判断，而是根据后面计算好的索引进行跳转，从而可以省略掉部分比较步骤

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70][]

经过上面分析，代码如下

private static int[] dailyTemperatures1(int[] T) {
            int length = T.length;
            int[] result = new int[length];
    
            //从右向左遍历
            for (int i = length - 2; i >= 0; i--) {
                //此处暴力的做法是执行j++,但是可以利用计算好的值执行j+=result[j]
                for (int j = i + 1; j < length; j += result[j]) {
                    //如果遇到的值已经大于i了，则直接计算索引
                    if (T[j] > T[i]) {
                        result[i] = j - i;
                        break;
                    } 
                   
                    //如果遇到的T[j] 已经小于 T[i],且result[j]已经是0，表示后面没有比T[j]大的值，当然也就没有比T[i]大的值
                    if (T[j] < T[i] && result[j] == 0) { 
                        result[i] = 0;
                        break;
                    }
                }
            }
            return result;
        }

利用前面计算好的结果，为后续遍历的结果提供参考。

解法三、利用单调递减栈，使用一个偶外的单调递减栈，栈中存储的是索引，索引所对应的温度递减。

（1）处理 index = 0 ，值为 73，因为栈是空的，所以索引 0 直接入栈

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 1][]

（2）处理 index = 1，值为 74 ，因为 T \[1\] > T\[stack.peek()\] (即T\[0\])，表示需要处理栈顶元素所代表位置的值

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 2][]

（3）处理 index = 2 ，值为 75 ，因为比栈顶元素大，所以和步骤2的处理时一样的

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 3][]

（4）处理index = 3，值为71，因为比栈顶元素小，所以元素直接入栈

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 4][]

其他的处理时类似的，此处就不在说明了，代码如下：

private static int[] dailyTemperatures(int[] T) {
            int length = T.length;
            int[] result = new int[length];
    
            //维护一个存储下标的单调栈，温度依次递减的，栈里面存储的是索引
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < length; ++i) {
                int temperature = T[i];
                //如果栈不为空，并且当前处理的值大于栈顶的值，则处理栈顶所以处对应的值，同时移除栈顶元素
                while (!stack.isEmpty() && temperature > T[stack.peek()]) {
                    int prevIndex = stack.pop();
                    result[prevIndex] = i - prevIndex;
                }
                stack.push(i);
            }
            return result;
        }

个人学习，有错误，麻烦指出，感谢。

注：题目描述来源于https://leetcode-cn.com/problems/daily-temperatures

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70]: /images/20221119/382733becc494ec790e3504c5d382240.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 1]: /images/20221119/aac26380dd0e46ec96568bbef311c8fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 2]: /images/20221119/d93a2b0586df4a0796eb79440c64474e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 3]: /images/20221119/075feaa95c1242bda25cc725779ff111.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 4]: /images/20221119/1b125b571e504316966e71a7c2cd9f1d.png