❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！
- 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航：
- LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
- 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
- python源码解读：解读python的源代码与调用关系，快速提升代码质量
- python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
题目描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
方法一：一次遍历
解题步骤：
- 初始化两个变量：
min_price为正无穷大，用于记录遍历过程中遇到的最低价格；max_profit为0，用于记录最大利润。 - 遍历价格数组，对于每个价格，更新
min_price，并计算以当前价格卖出的利润，更新max_profit。
Python 代码示例
def maxProfit(prices): min_price = float('inf') max_profit = 0 for price in prices: if price < min_price: min_price = price elif price - min_price > max_profit: max_profit = price - min_price return max_profit
方法一通过一次遍历来解决买卖股票的最佳时机问题，下面用 ASCII 图形来详细解释这个方法的工作原理。
一次遍历的图解
考虑一个具体的价格数组示例：
prices = [7, 1, 5, 3, 6, 4]
我们需要找到买入和卖出的最佳时机，以获取最大利润。下面的图解将展示如何在一次遍历中实现这一点。
初始状态
- 初始化
min_price为正无穷大。 - 初始化
max_profit为0。
遍历过程
初始: min_price = inf, max_profit = 0 第1天: price = 7 min_price = min(inf, 7) = 7 max_profit = max(0, 7 - 7) = 0 状态: min_price = 7, max_profit = 0 第2天: price = 1 min_price = min(7, 1) = 1 max_profit = max(0, 1 - 1) = 0 状态: min_price = 1, max_profit = 0 第3天: price = 5 min_price = min(1, 5) = 1 max_profit = max(0, 5 - 1) = 4 状态: min_price = 1, max_profit = 4 第4天: price = 3 min_price = min(1, 3) = 1 max_profit = max(4, 3 - 1) = 4 状态: min_price = 1, max_profit = 4 第5天: price = 6 min_price = min(1, 6) = 1 max_profit = max(4, 6 - 1) = 5 状态: min_price = 1, max_profit = 5 第6天: price = 4 min_price = min(1, 4) = 1 max_profit = max(5, 4 - 1) = 5 状态: min_price = 1, max_profit = 5
结果
- 最终得到的最大利润是
5，即在价格为1的第2天买入，在价格为6的第5天卖出。
总结步骤
- 初始化两个变量
min_price和max_profit。 - 遍历价格数组，更新
min_price为遇到的最小价格。 - 对每个价格，计算如果当天卖出的利润，并更新
max_profit。 - 最后的
max_profit就是最大利润。
这种方法简单而有效，只需一次遍历就能找到最大利润，同时也避免了复杂的计算和额外的空间开销。
方法二：动态规划
解题步骤：
- 使用一个数组
dp来记录每天结束时可能得到的最大利润。 - 第一天的利润为0；从第二天开始，更新当前最小购买价格，并计算当前可能的最大利润。
Python 代码示例
def maxProfit(prices): if not prices: return 0 n = len(prices) min_price = prices[0] max_profit = 0 for i in range(1, n): min_price = min(min_price, prices[i]) max_profit = max(max_profit, prices[i] - min_price) return max_profit
方法三：分治法
解题步骤：
- 将价格数组分为两部分，递归地找出左右两部分的最大利润。
- 计算跨越两部分的最大利润，即左侧的最低价格和右侧的最高价格之差。
- 最大利润是左侧、右侧和跨中三者的最大值。
Python 代码示例
def maxProfit(prices): def maxCrossingProfit(left, right): if left == right: return 0 mid = (left + right) // 2 min_left = min(prices[left:mid+1]) max_right = max(prices[mid+1:right+1]) return max(0, max_right - min_left) def divideAndConquer(left, right): if left >= right: return 0 mid = (left + right) // 2 left_profit = divideAndConquer(left, mid) right_profit = divideAndConquer(mid + 1, right) cross_profit = maxCrossingProfit(left, right) return max(left_profit, right_profit, cross_profit) return divideAndConquer(0, len(prices) - 1)
方法四：前缀最小值与后缀最大值
解题步骤：
- 创建两个数组，分别存储从左到右的前缀最小值和从右到左的后缀最大值。
- 遍历
prices数组，计算利用前缀最小和后缀最大计算可能的最大利润。
Python 代码示例
def maxProfit(prices): n = len(prices) if n == 0: return 0 min_prefix = [0] * n max_suffix = [0] * n min_prefix[0] = prices[0] for i in range(1, n): min_prefix[i] = min(min_prefix[i-1], prices[i]) max_suffix[n-1] = prices[n-1] for i in range(n-2, -1, -1): max_suffix[i] = max(max_suffix[i+1], prices[i]) max_profit = 0 for i in range(n): max_profit = max(max_profit, max_suffix[i] - min_prefix[i]) return max_profit
方法五：Kadane算法变形
解题步骤：
- 理解为找最大子数组和的问题，其中“价格差”数组是原数组相邻元素的差值。
- 使用Kadane算法找到最大子数组和，即为最大利润。
Python 代码示例
def maxProfit(prices): max_current = max_global = 0 for i in range(1, len(prices)): max_current = max(0, max_current + prices[i] - prices[i-1]) if max_current > max_global: max_global = max_current return max_global
算法分析
- 时间复杂度：所有方法均为 (O(n))，其中 (n) 是数组长度，因为每个方法都只遍历了一次或两次数组。
- 空间复杂度：
- 方法一和五：(O(1))，只使用了常数空间。
- 方法二、三和四：(O(n))，因为使用了额外的数组。
不同算法的优劣势对比
- 一次遍历（方法一）和Kadane算法变形（方法五）非常高效，简单，易于实现。
- 动态规划（方法二）直观，易于理解，常用于面试中解释。
- 分治法（方法三）和前缀最小值与后缀最大值（方法四）提供了不同的视角，适合深入理解问题的结构，但实现较为复杂。
应用示例
这些方法可以应用于金融分析领域，特别是在算法交易和股票市场分析中，用于计算和预测最优买卖点，从而最大化投资回报。
🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)
❤️❤️作者知识有限，如有错误，请各位大佬评论区批评指正，不胜感激❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉
