Python实现股票买卖最佳时机：从暴力法到贪心算法的优化
本文详细解析LeetCode中“买卖股票的最佳时机”问题。首先介绍基于双重循环的暴力求解法，分析其时间复杂度高的缺陷；随后引入贪心算法，通过局部最优推导全局最优，实现O(n)时间复杂度的高效解法。文章包含Python代码示例及原理图解，帮助读者理解算法优化思路。
题目背景与要求
开始进行LeetCode算法题的练习，今日选择的题目是“买卖股票的最佳时机”。
题目要求
给定一个整数数组，其中第 i 个元素代表某支股票在第 i 天的价格。
请设计一个算法来计算你能获取的最大利润。你可以进行多次交易（即可以多次买入和卖出同一支股票）。
需要注意的是，你不能同时参与多笔交易，这意味着在再次买入之前，必须先将之前持有的股票卖出。
暴力求解法及其局限性
面对这个题目，最直观的思路是采用蛮力法（暴力枚举）。
具体做法是通过两层循环，遍历所有可能的买入和卖出组合，计算不同天数之间的利润以及多次交易的利润总和。
以下是暴力法的代码实现：
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
self.allbuy1 = [] #单次买卖的差值数组 （可能为负）
self.allbuy2 = [] #所有可能买卖的利润数组 （可能为负）
# allbuy1和allbuy2的区别为一个是单次买卖 一个是多次买卖和
self.curbuy(prices,0,0) #prices 为价格表 0：初始 0：
#print(self.allbuy1)
#print(self.allbuy2)
return self.picBigest(self.allbuy2)
def buyticket(self,prilist,a,b): #list:放入的价格数组 a:上一次买入的价格 b:今天卖出的价格
return prilist[b] -prilist[a] #返回 赚取得价格
def curbuy(self,plist,x,result): #plist：价格数组 x:当天的数组坐标 result: 利润
obj=result #固定上一次的价格 保存为上一个递归
lens=len(plist) #天数
for i in range(x,lens-1):
for j in range(i+1,lens):
temp=self.buyticket(plist,i, j)
self.allbuy1.append(temp)
self.allbuy2.append(temp) #单次利润放入数组
result = obj + temp #将之前的利润加上今天的利润
if(x>=2): #如果买入是第2+1天以后 则可以加上之前的利润
self.allbuy2.append(result) #多次买卖利润放入数组
self.curbuy(plist,j+1,result) #递归 j+1:卖出的后一天 result:利润
def picBigest(self,reslist):
big=0
for i in reslist:
if (i>big):
big=i
print(big)
return big
if __name__ == '__main__':
test=Solution()
prices = [5,7,3,8] # 输入的每日股票数组
test.maxProfit(prices)代码分析：
这段代码逻辑简单直观，它将所有可能的交易组合及其利润都存入数组中，最后从中找出最大值。
然而，提交该代码时会提示“超出时间限制”。这是因为当输入数组长度非常大时，双重循环导致计算量呈指数级增长，从而引发性能错误。
——————————————————————————————————————————————————————————————————————————————
贪心算法原理与实现
因此，我们需要更换思路，利用贪心算法来解决这个问题。
首先简要介绍贪心算法的核心思想：在处理问题时，仅对当前情况做出最优选择，未来的变化不会影响之前的决定。简而言之，这是一个通过局部最优解逐步逼近全局最优解的过程。
为了便于理解，我们可以参考“找零钱”的例子。
假设现有面值为5元、2元、1元、5角、2角、1角的货币，需要找给顾客4元6角现金，目标是使付出的货币张数最少。
- 第一步，找出小于4元6角的最大面值，即2元。
- 第二步，剩余2元6角，再找出小于2元6角的最大面值，即2元。
- 第三步，剩余6角，找出小于6角的最大面值，即5角。
- 第四步，剩余1角，找出小于1角的最大面值，即1角。最终共付出4张纸币。
了解了贪心算法的基本思想后，我们将其应用到股票交易问题中。
在已知股票价格走势的情况下，我们只需判断下一天的价格变化：如果第二天价格高于今天，则今天买入、明天卖出；如果价格下跌，则不操作。通过这种策略，收益将保持稳步增长。
有人可能会质疑：是否可以选择不卖，等待几天后再卖，或者不买，等待几天后再买，这样也能保持增长吗？如图所示：
假设在第2天买入，第3天卖出，第4天买入，第5天卖出，总收益为A+B。
如果改为在第2天买入，一直持有到第5天卖出，总收益为C。
从图中可以明显看出，A+B大于C。因此，贪心算法在这种情况下非常适用，并且能保证得到最优解。
以下是贪心算法的代码实现：
class Solution(object):
def maxProfit(self, prices):
profit = 0
for day in range(len(prices)-1):
differ = prices[day+1] - prices[day]
if differ > 0:
profit += differ
return profit
if __name__ == '__main__':
test=Solution()
prices = [5,7,3,9] # 输入的每日股票数组
print(test.maxProfit(prices))以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
