leetcode
leetcode 2951 ~ 3000
每日温度

每日温度

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 100 ms, 内存: 22.9 MB


/*
题目思路:
Java Stream 主要用于处理集合类数据,但在这个问题上,由于需要处理每个元素与之前的元素之间的关系,Stream 并不是特别合适。
然而,我们可以利用一些辅助数据结构,例如栈,来实现这个功能。
*/

import java.util.stream.IntStream;
import java.util.Stack;

public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        IntStream.range(0, n).forEach(i -> {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int index = stack.pop();
                result[index] = i - index;
            }
            stack.push(i);
        });
        return result;
    }
}

解释

方法:

此题解采用了单调栈的方法。单调栈用于维护一个元素索引的栈,索引对应的温度值是单调递减的。遍历温度列表,对于每一个温度,如果当前温度大于栈顶温度,说明找到了栈顶元素的第一个更高的温度,此时将栈顶元素索引弹出,并计算当前索引与栈顶索引的差值,作为答案数组对应位置的值。如果当前温度小于等于栈顶温度,或者栈为空,则把当前温度的索引压入栈。最后,栈中剩余的索引对应的温度值在右侧没有更高的温度值,答案数组默认已经初始化为0,因此不需要额外操作。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在单调栈中,为什么选择栈顶元素的温度必须保持单调递减?
单调栈中保持栈顶元素的温度单调递减的原因是为了正确地记录每个温度第一次出现更高温度的天数。栈中保存的是温度的索引,且对应的温度是递减的。当遇到一个新的温度比栈顶的温度高时,可以确定栈顶的温度在这一天后第一次遇到了更高的温度,因此可以计算两天的差值,然后更新答案数组。如果栈不是单调递减的,则无法保证这样的逻辑关系,会导致无法正确计算出正确的天数。
🦆
如果当前温度等于栈顶温度时,为什么没有处理这种情况,它会影响结果吗?
在题解中,如果当前温度等于栈顶温度,这种情况并没有特别处理,因为这并不影响结果。在算法逻辑中,我们主要关心的是找到一个'更高'的温度。等于栈顶温度的情况下,不弹出栈顶元素,因为我们还没有遇到一个更高的温度来更新之前温度的等待天数。当前温度的索引简单地被添加到栈中,这样,栈中可能会有连续的相同温度的索引,但这不会影响结果,因为我们只在遇到更高温度时才处理和更新答案数组。
🦆
代码中的while循环会在什么条件下结束?如果温度列表是单调递增的,栈的行为会怎样?
代码中的while循环会在栈为空或当前温度不再大于栈顶温度的情况下结束。如果温度列表是单调递增的,栈的行为将是不断地将新的索引压入栈中,因为永远不会有一个当前温度小于或等于栈顶温度的情况。这意味着栈将持续增长,直到遍历完成。在这种情况下,由于没有任何元素能被弹出来更新答案数组,栈中的元素在最后都不会有更高温度的天数,答案数组的所有值将保持初始化的0。

相关问题