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^40 <= prices[i] <= 10^4
122.2 题解
贪心算法
// 方法一：贪心算法
// 只要今天的价格比昨天高，就买入昨天卖出，最后总和为最大利润
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;
}
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
