739.每日温度

LeetCode LeetCode 数组 热题100 栈 单调栈
发布时间 :
字数:2.8k 阅读 : 评论:
  1. 739.每日温度
    1. 739.1 题目
    2. 739.2 题解
      1. 方法一：单调栈
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：从后向前遍历
        1. 思路
        2. 复杂度分析
        3. 代码
      3. 方法三：暴力解法（不推荐）
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 739.3 代码
    4. 739.4 运行结果

739.每日温度

739.1 题目

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

提示：

  • 1 <= temperatures.length <= 10^5
  • 30 <= temperatures[i] <= 100

739.2 题解

方法一：单调栈

思路

使用栈存储尚未找到下一个更高温度的索引。遍历温度数组，当当前温度大于栈顶索引对应的温度时，弹出栈顶并计算天数差值。将当前索引入栈，继续处理后续温度。栈中维护的是单调递减的温度索引序列。

核心思想：单调递减栈，存储待找到更高温度的索引。

具体步骤：

  1. 初始化结果数组和空栈。
  2. 遍历温度数组：
    • 当栈非空且当前温度 > 栈顶索引对应的温度：
      • 弹出栈顶索引，计算天数差值
    • 将当前索引入栈
  3. 栈中剩余索引对应的结果为 0。

举例：对于 temperatures = [73,74,75,71,69,72,76,73]：

  • i=0：栈 [0]
  • i=1：74 > 73，弹出 0，answer[0] = 1，栈 [1]
  • i=2：75 > 74，弹出 1，answer[1] = 1，栈 [2]
  • i=3：71 < 75，栈 [2,3]
  • i=4：69 < 71，栈 [2,3,4]
  • i=5：72 > 69，弹出 4，answer[4] = 1；72 > 71，弹出 3，answer[3] = 2；栈 [2,5]
  • i=6：76 > 72，弹出 5，answer[5] = 1；76 > 75，弹出 2，answer[2] = 4；栈 [6]
  • i=7：73 < 76，栈 [6,7]
  • 结果：[1,1,4,2,1,1,0,0]

复杂度分析

  • 时间复杂度：O(n)，每个元素最多入栈出栈各一次。
  • 空间复杂度：O(n)，最坏情况下栈存储所有索引。

代码

// 方法一：使用栈
// 栈存储未找到下一个更高温度的索引：使用栈来存储尚未找到下一个更高温度的天数索引。当遍历到一个新的温度时，将其索引与栈顶元素索引进行比较。
// 比较并更新结果数组：如果当前温度高于栈顶元素所指的温度，则说明找到了栈顶元素的下一个更高温度，弹出栈顶元素并计算天数差值更新结果数组。
// 将当前索引入栈：无论当前温度是否高于栈顶元素的温度，都将当前索引入栈，以便后续继续比较。
static int[] DailyTemperatures1(int[] temperatures)
{
    // 获取温度数组的长度
    int temperaturesLength = temperatures.Length;

    // 创建一个数组用于存放结果
    int[] answer = new int[temperaturesLength];

    // 创建一个栈用于存放未处理的温度索引
    Stack<int> stack = new Stack<int>();

    // 遍历温度数组
    for (int i = 0; i < temperaturesLength; i++)
    {
        // 当栈不为空且当前温度大于栈顶索引对应的温度时 有可能一个栈存了多个元素
        while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()])
        {
            // 弹出栈顶索引
            int index = stack.Pop();

            // 计算当前索引与弹出索引的差值，更新结果数组
            answer[index] = i - index;
        }

        // 将当前索引压入栈中
        stack.Push(i);
    }

    // 返回结果数组
    return answer;
}

方法二：从后向前遍历

思路

从倒数第二个元素开始向前遍历，利用已计算的结果进行跳跃：如果后面已计算过且有下一个更高温度，可直接跳到该位置继续查找。

避免重复比较，提高效率。

举个例子：temperatures = [73,74,75,71,69,72,76,73]

  • 从后往前，answer[7]=0
  • i=6（76）：后面没有更高温度，answer[6]=0
  • i=5（72）：后面 76>72，answer[5]=1
  • i=4（69）：下一个位置 72>69，answer[4]=1（只需等 1 天到索引 5，不是 2）
  • …

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

代码

// 方法二：从后向前遍历
// 从后往前遍历：从倒数第二个元素开始向前遍历，每个元素查找其后第一个比当前温度高的温度。
// 跳跃索引以优化查找：在查找过程中，如果后面已经计算过的温度有下一个更高温度，可以直接跳跃索引加速查找。
static int[] DailyTemperatures2(int[] temperatures)
{
    // 获取温度数组的长度
    int temperaturesLength = temperatures.Length;

    // 创建一个数组用于存放结果
    int[] answer = new int[temperaturesLength];

    // 从倒数第二个元素开始遍历数组
    for (int i = temperaturesLength - 2; i >= 0; i--)
    {
        // 初始化比较索引为当前索引的下一个
        int j = i + 1;

        // 查找第一个比当前温度高的温度
        while (j < temperaturesLength && temperatures[i] >= temperatures[j])
        {
            // 如果答案数组中保存了非零的差值，直接跳到该索引
            if (answer[j] > 0)
            {
                j += answer[j];
            }
            // 如果答案数组中保存的是零，说明之后没有更高温度
            else
            {
                j = temperaturesLength;
            }
        }

        // 如果找到更高温度，计算差值并更新结果数组
        if (j < temperaturesLength)
        {
            answer[i] = j - i;
        }
    }

    // 返回结果数组
    return answer;
}

方法三：暴力解法（不推荐）

思路

对每个温度，向后遍历查找第一个更高的温度，找到后计算天数差值并记录。

简单直观，但时间复杂度高，大数据量会超时。

举个例子：temperatures = [73,74,75,71,69,72,76,73]

  • i=0，73：向后找，74>73，answer[0]=1
  • i=1，74：向后找，75>74，answer[1]=1
  • i=2，75：向后找，76>75，answer[2]=4
  • …

复杂度分析

  • 时间复杂度：O(n²)
  • 空间复杂度：O(n)

代码

// 方法三：暴力解法 不推荐
static int[] DailyTemperatures3(int[] temperatures)
{
    // 创建一个数组用于存放结果
    int[] answer = new int[temperatures.Length];

    // 遍历温度数组
    for (int i = 0; i < temperatures.Length; i++)
    {
        // 初始化当前索引的结果为0
        answer[i] = 0;

        // 查找第一个比当前温度高的温度
        for (int j = i; j < temperatures.Length; j++)
        {
            // 如果找到更高温度，计算差值并更新结果数组
            if (temperatures[j] > temperatures[i])
            {
                answer[i] = j - i;
                break; // 找到更高温度后，退出内层循环
            }
        }
    }

    // 返回结果数组
    return answer;
}

739.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

        #endregion

        #region 测试

        // 示例 1
        int[] temperatures1 = { 73, 74, 75, 71, 69, 72, 76, 73 };
        int[] result1_1 = DailyTemperatures1(temperatures1);
        Console.WriteLine($"示例1 方法1 输出：{string.Join(",", result1_1)}");
        int[] result1_2 = DailyTemperatures2(temperatures1);
        Console.WriteLine($"示例1 方法2 输出：{string.Join(",", result1_2)}");

        // 示例 2
        int[] temperatures2 = { 30, 40, 50, 60 };
        int[] result2_1 = DailyTemperatures1(temperatures2);
        Console.WriteLine($"示例2 方法1 输出：{string.Join(",", result2_1)}");
        int[] result2_2 = DailyTemperatures2(temperatures2);
        Console.WriteLine($"示例2 方法2 输出：{string.Join(",", result2_2)}");

        // 示例 3
        int[] temperatures3 = { 30, 60, 90 };
        int[] result3_1 = DailyTemperatures1(temperatures3);
        Console.WriteLine($"示例3 方法1 输出：{string.Join(",", result3_1)}");
        int[] result3_2 = DailyTemperatures2(temperatures3);
        Console.WriteLine($"示例3 方法2 输出：{string.Join(",", result3_2)}");

        #endregion
    }

    #region 答案

    // 方法一：使用栈
    // 栈存储未找到下一个更高温度的索引：使用栈来存储尚未找到下一个更高温度的天数索引。当遍历到一个新的温度时，将其索引与栈顶元素索引进行比较。
    // 比较并更新结果数组：如果当前温度高于栈顶元素所指的温度，则说明找到了栈顶元素的下一个更高温度，弹出栈顶元素并计算天数差值更新结果数组。
    // 将当前索引入栈：无论当前温度是否高于栈顶元素的温度，都将当前索引入栈，以便后续继续比较。
    static int[] DailyTemperatures1(int[] temperatures)
    {
        // 获取温度数组的长度
        int temperaturesLength = temperatures.Length;

        // 创建一个数组用于存放结果
        int[] answer = new int[temperaturesLength];

        // 创建一个栈用于存放未处理的温度索引
        Stack<int> stack = new Stack<int>();

        // 遍历温度数组
        for (int i = 0; i < temperaturesLength; i++)
        {
            // 当栈不为空且当前温度大于栈顶索引对应的温度时 有可能一个栈存了多个元素
            while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()])
            {
                // 弹出栈顶索引
                int index = stack.Pop();

                // 计算当前索引与弹出索引的差值，更新结果数组
                answer[index] = i - index;
            }

            // 将当前索引压入栈中
            stack.Push(i);
        }

        // 返回结果数组
        return answer;
    }

    // 方法二：从后向前遍历
    // 从后往前遍历：从倒数第二个元素开始向前遍历，每个元素查找其后第一个比当前温度高的温度。
    // 跳跃索引以优化查找：在查找过程中，如果后面已经计算过的温度有下一个更高温度，可以直接跳跃索引加速查找。
    static int[] DailyTemperatures2(int[] temperatures)
    {
        // 获取温度数组的长度
        int temperaturesLength = temperatures.Length;

        // 创建一个数组用于存放结果
        int[] answer = new int[temperaturesLength];

        // 从倒数第二个元素开始遍历数组
        for (int i = temperaturesLength - 2; i >= 0; i--)
        {
            // 初始化比较索引为当前索引的下一个
            int j = i + 1;

            // 查找第一个比当前温度高的温度
            while (j < temperaturesLength && temperatures[i] >= temperatures[j])
            {
                // 如果答案数组中保存了非零的差值，直接跳到该索引
                if (answer[j] > 0)
                {
                    j += answer[j];
                }
                // 如果答案数组中保存的是零，说明之后没有更高温度
                else
                {
                    j = temperaturesLength;
                }
            }

            // 如果找到更高温度，计算差值并更新结果数组
            if (j < temperaturesLength)
            {
                answer[i] = j - i;
            }
        }

        // 返回结果数组
        return answer;
    }

    // 方法三：暴力解法 不推荐
    static int[] DailyTemperatures3(int[] temperatures)
    {
        // 创建一个数组用于存放结果
        int[] answer = new int[temperatures.Length];

        // 遍历温度数组
        for (int i = 0; i < temperatures.Length; i++)
        {
            // 初始化当前索引的结果为0
            answer[i] = 0;

            // 查找第一个比当前温度高的温度
            for (int j = i; j < temperatures.Length; j++)
            {
                // 如果找到更高温度，计算差值并更新结果数组
                if (temperatures[j] > temperatures[i])
                {
                    answer[i] = j - i;
                    break; // 找到更高温度后，退出内层循环
                }
            }
        }

        // 返回结果数组
        return answer;
    }

    #endregion
}

739.4 运行结果

示例1 方法1 输出：1,1,4,2,1,1,0,0
示例1 方法2 输出：1,1,4,2,1,1,0,0
示例2 方法1 输出：1,1,1,0
示例2 方法2 输出：1,1,1,0
示例3 方法1 输出：1,1,0
示例3 方法2 输出：1,1,0
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏