股票买卖最佳时机leetcode 365 lab8:365 lab8

股票买卖最佳时机是LeetCode上的一道经典问题，主要涉及动态规划、数组处理以及贪心算法等编程知识点。在这个问题中，我们被给予一个整数数组prices，表示一只股票在不同天的价格，目标是找到最佳的买卖时机，使得在交易过程中获得的最大利润。

1. 动态规划：动态规划是一种解决最优化问题的有效方法，它通过将原问题分解为子问题，然后逐步构建最优解。在股票买卖问题中，我们可以定义两个变量，buyDay（购买股票的天数）和maxProfit（当前的最大利润），用动态规划的方法来遍历数组。对于每一天，我们都考虑两种情况：不买股票和买股票。如果不买股票，那么我们保持现有的最大利润；如果买股票，我们需要计算出买入后的最大可能利润，即prices[i] - prices[buyDay] + maxProfit。

2. 贪心算法：贪心算法通常是在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最优。在股票买卖问题中，贪心策略可能是每次遇到价格下降时就卖出股票，然后在价格更低时再次买入。然而，这种方法并不总是最优，因为它没有考虑到未来价格可能会上升的情况。

3. 数组处理：在处理股票价格数组时，我们需要对数组进行遍历，同时记录一些关键信息，如最低购买价格和当前最大利润。可以使用两个变量来跟踪这些信息，例如minPrice用于存储到目前为止的最低价格，maxProfit用于存储最大利润。

4. 代码实现：在Python中，这个问题可以简洁地用一两行代码解决。以下是一个简单的解决方案：

def maxProfit(prices):

 if not prices: return 0

 min_price = prices[0]

 max_profit = 0

 for price in prices:

 min_price = min(min_price, price)

 max_profit = max(max_profit, price - min_price)

 return max_profit

这段代码首先检查价格数组是否为空，然后初始化最低价格和最大利润，接着遍历价格数组，更新最低价格和最大利润。

1. 复杂度分析：时间复杂度是O(n)，因为我们只遍历一次数组。空间复杂度是O(1)，因为只使用了常数个额外的空间。

2. 扩展思考：这个问题还有其他变种，比如限制只能交易一次或最多交易两次等，这些情况可能需要不同的策略和算法。例如，如果限制只能交易一次，那么我们只需要找到数组中的最小值和最大值，然后相减即可得到最大利润。