739.每日温度

LeetCode LeetCode 数组 栈 单调栈
发布时间 :
字数:2.1k 阅读 : 评论:
  1. 739.每日温度
    1. 739.1 题目
    2. 739.2 题解
      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 题解

使用栈

// 方法一：使用栈
// 栈存储未找到下一个更高温度的索引：使用栈来存储尚未找到下一个更高温度的天数索引。当遍历到一个新的温度时，将其索引与栈顶元素索引进行比较。
// 比较并更新结果数组：如果当前温度高于栈顶元素所指的温度，则说明找到了栈顶元素的下一个更高温度，弹出栈顶元素并计算天数差值更新结果数组。
// 将当前索引入栈：无论当前温度是否高于栈顶元素的温度，都将当前索引入栈，以便后续继续比较。
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;
}

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-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏