122.买卖股票的最佳时机II

LeetCode LeetCode 数组贪心动态规划

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

字数:2k 阅读 :

评论:

122.买卖股票的最佳时机II

122.买卖股票的最佳时机II

122.1 题目

给你一个整数数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出，利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，利润 = 6 - 3 = 3。
总利润为 4 + 3 = 7。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出，利润 = 5 - 1 = 4。
总利润为 4。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下，交易无法获得正利润，所以最大利润为 0。

提示：

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

122.2 题解

方法一：贪心算法

思路

这道题和121题的区别是：可以买卖多次。那怎么才能利润最大化呢？

答案是：抓住每一次上涨的机会。只要今天比昨天贵，就昨天买今天卖。虽然现实中不能同一天卖出再买入，但数学上等价于在所有上涨区间都进行交易。

比如价格序列 [1,2,3,4,5]：

方法1：第1天买，第5天卖，利润 = 5-1 = 4
方法2（贪心）：每天买卖，利润 = (2-1)+(3-2)+(4-3)+(5-4) = 4

两种方法利润相同！贪心法把大利润拆成了多个小利润的和。

举个例子：prices = [7,1,5,3,6,4]

1→5：上涨4，利润+4
3→6：上涨3，利润+3
总利润 = 4 + 3 = 7

复杂度分析

时间复杂度：O(n)，遍历一次数组
空间复杂度：O(1)，只使用常数变量

代码

// 方法一：贪心算法
// 只要今天的价格比昨天高，就买入昨天卖出，最后总和为最大利润
static int MaxProfit1(int[] prices)
{
    int maxProfit = 0; // 初始化最大利润为0

    // 从第二天开始遍历价格数组
    for (int i = 1; i < prices.Length; i++)
    {
        // 如果今天的价格比昨天高，就买入昨天卖出，利润累加
        if (prices[i] > prices[i - 1])
        {
            maxProfit += prices[i] - prices[i - 1];
        }
    }

    // 返回最大利润
    return maxProfit;
}

方法二：峰谷法

思路

更直观的想法：在波谷买入，在波峰卖出。找到每个上升区间的起点和终点，计算利润。

具体做法：

找到局部最低点（波谷）买入
找到局部最高点（波峰）卖出
计算这段区间的利润
继续寻找下一个波谷和波峰

举个例子：prices = [7,1,5,3,6,4]

波谷：1（第2天），波峰：5（第3天），利润4
波谷：3（第4天），波峰：6（第5天），利润3
总利润 = 4 + 3 = 7

这个方法和贪心法本质相同，只是更直观地展示了”低买高卖”的过程。

复杂度分析

时间复杂度：O(n)，每个元素最多被访问两次
空间复杂度：O(1)，只使用常数变量

代码

// 方法二：峰谷法
// 寻找每次买入和卖出的低点和高点，计算每次的利润总和
static int MaxProfit2(int[] prices)
{
    int maxProfit = 0; // 初始化最大利润为0
    int valley = prices[0]; // 初始化低点为第一天的价格
    int peak = prices[0]; // 初始化高点为第一天的价格
    int i = 0; // 初始化索引为0

    // 遍历价格数组，寻找每次的低点和高点
    while (i < prices.Length - 1)
    {
        // 找到当前的低点
        while (i < prices.Length - 1 && prices[i] >= prices[i + 1])
            i++;
        valley = prices[i];

        // 找到当前的高点
        while (i < prices.Length - 1 && prices[i] <= prices[i + 1])
            i++;
        peak = prices[i];

        // 计算当前区间的利润并累加到最大利润
        maxProfit += peak - valley;
    }

    // 返回最大利润
    return maxProfit;
}

122.3 代码

using System;

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

        // 122. 买卖股票的最佳时机 II
        // 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
        // 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。
        // 你也可以先购买，然后在 同一天 出售。
        // 返回你能获得的最大利润。

        // 示例 1：
        // 输入：prices = [7,1,5,3,6,4]
        // 输出：7
        // 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
        //      随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
        //      总利润为 4 + 3 = 7 。

        // 示例 2：
        // 输入：prices = [1,2,3,4,5]
        // 输出：4
        // 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
        //      总利润为 4 。

        // 示例 3：
        // 输入：prices = [7,6,4,3,1]
        // 输出：0
        // 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

        // 提示：
        // 1 <= prices.length <= 3 * 10^4
        // 0 <= prices[i] <= 10^4

        #endregion

        #region 测试

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

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

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

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

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

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

        #endregion
    }

    #region 答案

    // 方法一：贪心算法
    // 只要今天的价格比昨天高，就买入昨天卖出，最后总和为最大利润
    static int MaxProfit1(int[] prices)
    {
        int maxProfit = 0; // 初始化最大利润为0

        // 从第二天开始遍历价格数组
        for (int i = 1; i < prices.Length; i++)
        {
            // 如果今天的价格比昨天高，就买入昨天卖出，利润累加
            if (prices[i] > prices[i - 1])
            {
                maxProfit += prices[i] - prices[i - 1];
            }
        }

        // 返回最大利润
        return maxProfit;
    }

    // 方法二：峰谷法
    // 寻找每次买入和卖出的低点和高点，计算每次的利润总和
    static int MaxProfit2(int[] prices)
    {
        int maxProfit = 0; // 初始化最大利润为0
        int valley = prices[0]; // 初始化低点为第一天的价格
        int peak = prices[0]; // 初始化高点为第一天的价格
        int i = 0; // 初始化索引为0

        // 遍历价格数组，寻找每次的低点和高点
        while (i < prices.Length - 1)
        {
            // 找到当前的低点
            while (i < prices.Length - 1 && prices[i] >= prices[i + 1])
                i++;
            valley = prices[i];

            // 找到当前的高点
            while (i < prices.Length - 1 && prices[i] <= prices[i + 1])
                i++;
            peak = prices[i];

            // 计算当前区间的利润并累加到最大利润
            maxProfit += peak - valley;
        }

        // 返回最大利润
        return maxProfit;
    }

    #endregion
}

122.4 运行结果

示例1 方法1 输出：7
示例1 方法2 输出：7
示例2 方法1 输出：4
示例2 方法2 输出：4
示例3 方法1 输出：0
示例3 方法2 输出：0

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