121.卖股票的最佳时机

LeetCode LeetCode 数组动态规划

发布时间 : 2000-01-10 01:02

字数:1.6k 阅读 :

评论:

121.卖股票的最佳时机

121.卖股票的最佳时机

121.1 题目

给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6，因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下，没有交易完成，所以最大利润为 0。

提示：

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4

121.2 题解

暴力法两层循环遍历所有组合

// 方法一：暴力法两层循环遍历所有组合
// 遍历所有的买入和卖出组合，找到最大的利润
static int MaxProfit1(int[] prices)
{
    // 初始化最大利润为0
    int result = 0;

    // 外层循环遍历所有可能的买入日期（股票价格数组的索引）
    for (int i = 0; i < prices.Length - 1; i++)
    {
        // 内层循环遍历在当前买入日期之后的所有可能的卖出日期
        for (int j = i + 1; j < prices.Length; j++)
        {
            // 计算当前买入日期和卖出日期的差价，即利润
            int currentProfit = prices[j] - prices[i];

            // 更新最大利润，取当前利润和之前最大利润的较大值
            result = Math.Max(result, currentProfit);
        }
    }

    // 返回计算得到的最大利润
    return result;
}

一次遍历记录最小买入值和最大利润

// 方法二：一次遍历记录最小买入值和最大利润
// 使用一次遍历，维护一个最小买入价格和最大利润
static int MaxProfit2(int[] prices)
{
    // 初始化一个变量 min 为整型的最大值，用于存储股票的最低价格
    int min = int.MaxValue;

    // 初始化一个变量 maxProfit 为 0，用于存储最大利润
    int maxProfit = 0;

    // 使用 for 循环遍历 prices 数组的每一个元素
    for (int i = 0; i < prices.Length; i++)
    {
        // 更新 min 的值为当前 min 和当前价格 prices[i] 中的较小值
        // 这一步用于找到截至当前为止的最低价格
        min = Math.Min(min, prices[i]);
    
        // 更新 maxProfit 的值为当前 maxProfit 和当前价格 prices[i] 与 min 之差中的较大值
        // 这一步用于计算当前价格卖出时能获得的最大利润
        maxProfit = Math.Max(maxProfit, prices[i] - min);
    }

    // 返回计算得到的最大利润
    return maxProfit;
}

121.3 代码

using System;

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

        // 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
        // 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。
        // 设计一个算法来计算你所能获取的最大利润。
        // 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

        // 示例 1：
        // 输入：[7,1,5,3,6,4]
        // 输出：5
        // 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。
        // 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

        // 示例 2：
        // 输入：prices = [7,6,4,3,1]
        // 输出：0
        // 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

        #endregion

        #region 测试

        // 示例 1
        int[] prices1 = { 7, 1, 5, 3, 6, 4 };
        int result1_1 = MaxProfit1(prices1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        int result1_2 = MaxProfit2(prices1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] prices2 = { 7, 6, 4, 3, 1 };
        int result2_1 = MaxProfit1(prices2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        int result2_2 = MaxProfit2(prices2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：暴力法两层循环遍历所有组合
    // 遍历所有的买入和卖出组合，找到最大的利润
    static int MaxProfit1(int[] prices)
    {
        // 初始化最大利润为0
        int result = 0;

        // 外层循环遍历所有可能的买入日期（股票价格数组的索引）
        for (int i = 0; i < prices.Length - 1; i++)
        {
            // 内层循环遍历在当前买入日期之后的所有可能的卖出日期
            for (int j = i + 1; j < prices.Length; j++)
            {
                // 计算当前买入日期和卖出日期的差价，即利润
                int currentProfit = prices[j] - prices[i];

                // 更新最大利润，取当前利润和之前最大利润的较大值
                result = Math.Max(result, currentProfit);
            }
        }

        // 返回计算得到的最大利润
        return result;
    }

    // 方法二：一次遍历记录最小买入值和最大利润
    // 使用一次遍历，维护一个最小买入价格和最大利润
    static int MaxProfit2(int[] prices)
    {
        // 初始化一个变量 min 为整型的最大值，用于存储股票的最低价格
        int min = int.MaxValue;
    
        // 初始化一个变量 maxProfit 为 0，用于存储最大利润
        int maxProfit = 0;

        // 使用 for 循环遍历 prices 数组的每一个元素
        for (int i = 0; i < prices.Length; i++)
        {
            // 更新 min 的值为当前 min 和当前价格 prices[i] 中的较小值
            // 这一步用于找到截至当前为止的最低价格
            min = Math.Min(min, prices[i]);
        
            // 更新 maxProfit 的值为当前 maxProfit 和当前价格 prices[i] 与 min 之差中的较大值
            // 这一步用于计算当前价格卖出时能获得的最大利润
            maxProfit = Math.Max(maxProfit, prices[i] - min);
        }
    
        // 返回计算得到的最大利润
        return maxProfit;
    }

    
    #endregion
}

121.4 运行结果

示例1 方法1 输出：5
示例1 方法2 输出：5
示例2 方法1 输出：0
示例2 方法2 输出：0

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