LeeCode每日一题--买卖股票的最佳时机
【前言】坚持日更LeeCode刷题系列
不积跬步,无以至千里;不积小流,无以成江海。愿与诸君共勉！
【题目】121.买卖股票的最佳时机
题目描述：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例:
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
思路一:我们很容易想到暴力求解的方法，即用两层循环对列表进行遍历，每次找到比当前最大利润大的值，则将其赋值给它，否则继续循环。具体代码如下：
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices)==0 or len(prices)==1:
return 0
else:
profit_max = 0
for i in range(len(prices)-1): #从第一天遍历到倒数第二天
for j in range(i,len(prices)): #从第i天遍历到最后一天
if prices[j]-prices[i] > profit_max: #如果得到更高的利润，则将其赋值给profit_max
profit_max = prices[j]-prices[i]
return profit_max
运行结果：出现了超时错误，显然采用两层循环的方式，时间复杂度为O(n^2)，因此对于过长的列表时，会出现超时的现象。
思路二:那么我们怎么优化呢？？？先不急，我们先思考下我们在上一个思路中为什么要循环两次呢？因为是要得到最高的利润，那么我们在上面从第二个循环中从第i天遍历到最后一天则是为了寻找到卖出股票的最佳时机，那么不难推测第一个循环则是为了得到最佳的买入时间。那么请接着往下思考，如果我们每次都记录下买入的最低价格，与当前价格作比较，选择出到底是第i天买入还是记录的价格日买入，那么循环的次数一次即可解决问题。具体内容如下：
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
min_price = float("inf") #初始化最低买入价格
max_profit = 0 #初始化最大利润
for i in range(len(prices)):
if prices[i] max_profit: #记录最大利润
max_profit = prices[i] - min_price
return max_profit
运行结果：
思路三:我们再次转化下思路，如果我们将所有的当天与前一天价格的差值算出来，例如：股票原本价格[7,1,5,3,6,3]，那么差值为[-6，4，-2，3，-2]，因为里面的数值代表着收益与亏损的情况，因此我们算出连续子数和的最大值即可得到最大利润。最大连续子序和可参考我的这篇文章。
关于其中一些知识的链接：
算法题解
分享就到这里了，欢迎大家一起交流讨论。
注明：
题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
作者：Mingw_
