如何解决LeetCode每日温度问题的Time limit exceeded错误？不用栈可行吗？

问题背景 #

我是编程初学者，尝试不使用栈解决LeetCode每日温度问题。该问题示例输入为：temperatures = [73,74,75,71,69,72,76,73]，输出为：[1,1,4,2,1,1,0,0]。我编写了如下代码，但在一个测试用例上失败，出现Time limit exceeded错误，想请教如何解决该超时问题，以及不用栈是否可行？

我的代码：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) 
    {
        int l=temperatures.length;
        int answer[]=new int[l];
        int i;
        for(i=0;i<l;i++)
        {
            int c=0;int j;int f=0;
            if(i==l-1)
            answer[i]=0;
            else
            {
            for(j=i+1;j<l;j++)
            {
                if(temperatures[i]<temperatures[j])
                {
                    c++;
                    f=1;
                    break;
                }
                if(temperatures[i]>=temperatures[j])
                {
                    c++;
                    f=0;
                }
            }
            if(f!=0)
            answer[i]=c;
            else
            answer[i]=0;
            }
        }
        return answer;
    }
}

解答 #

不用栈完全可行 #

不用栈解决这个问题是完全可以的，核心是找到时间复杂度更低的方法，避开暴力遍历带来的超时问题。

原代码超时原因 #

你当前的代码是双重循环暴力解法，时间复杂度为O(n²)。当测试用例的温度数组长度达到10^5级别时，计算量会指数级增长，直接触发超时限制。

优化方案：反向遍历+温度位置记录 #

我们可以采用反向遍历+维护温度最近出现位置的方法，把时间复杂度降到O(n)，具体思路如下：

• 从数组末尾往前遍历，复用已经计算好的后续位置信息
• 维护一个数组next，记录每个温度值最近一次出现的索引（温度范围固定在30~100，数组大小设为101足够）
• 对于当前温度temp，遍历所有比它高的温度值，找到其中最小的索引，该索引与当前索引的差值即为答案
• 每次遍历后，更新next数组，将当前温度对应的索引设为当前位置

优化后的代码：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        // 初始化next数组为n（表示未找到对应温度的位置）
        int[] next = new int[101];
        for (int i = 0; i < 101; i++) {
            next[i] = n;
        }

        // 从后往前遍历
        for (int i = n - 1; i >= 0; i--) {
            int temp = temperatures[i];
            int minIndex = n;
            // 查找比当前温度高的所有温度中，最近的位置
            for (int t = temp + 1; t <= 100; t++) {
                if (next[t] < minIndex) {
                    minIndex = next[t];
                }
            }
            // 计算结果：找到有效位置则取差值，否则为0
            answer[i] = minIndex != n ? minIndex - i : 0;
            // 更新当前温度的最近位置
            next[temp] = i;
        }
        return answer;
    }
}

补充说明 #

上面的解法中，内层遍历最多执行70次（温度范围30~100），属于固定次数的O(1)操作，整体时间复杂度仍为O(n)，完全可以通过所有测试用例。

内容的提问来源于stack exchange，提问作者sus-sus