Best Time to Buy and Sell Stock
你会得到一个列表 prices，其中 prices[i] 是第 i 天一只股票的价格。你可以在某一天买入一股，并在之后的某一天卖出。返回你能获得的最大利润；如果所有可能的交易都会亏钱，则返回 0。
函数
- pricesinteger-array
- 按顺序列出股票每天的价格
- 返回值integer
- 一次买入并在之后卖出所能获得的最大利润，或 0
约束条件
1 ≤ prices.length ≤ 1050 ≤ prices[i] ≤ 104- 你最多只能进行一次交易，并且卖出的日期必须晚于买入的日期。
示例
- 输入
- prices = [7, 2, 5, 9, 1, 4]
- 输出
- 7
- 解释
- 第 1 天以 2 买入，第 3 天以 9 卖出，获利 7。最低价 1 出现在第 4 天，晚于价格 9，因此在最低价之后卖出，最多只能获利 3。
- 输入
- prices = [9, 7, 4, 3, 1]
- 输出
- 0
- 解释
- 价格每天都在下跌，所以每次卖出价格都会低于买入价格。你没有进行交易，利润为 0。
进阶
如果你可以随意进行多次交易，但同一时间最多持有一股股票呢？
提示
逐个打开提示，每个都会多透露一点。
卖出总是在买入之后。选择一个卖出日：对应的哪一天买入能获得最大利润？
对于给定的卖出日，最佳买入日是它之前价格最低的一天。向前遍历时，只要记住这一天，就不必每次都重新查找。
按顺序遍历每一天，并记录两个数字：截至目前的最低价格和截至目前的最高利润。每天都比较当天价格减去最低价格后的结果与最高利润，然后更新最低价格。
题解
你必须先买入再卖出，所以答案不是最高价减去最低价。对于每个可以卖出的日子，最佳买入时机都是它之前价格最低的那一天。向前遍历时记录最低价格，就能只遍历一遍解决这个问题。
尝试每一对买入和卖出组合
结果正确，但无法在最大的测试中运行完毕
思路
每笔交易都包含买入日和之后的卖出日，所以要尝试每一对日期，并保留差值最大的那一对。将最佳利润初始值设为 0，就涵盖了不交易的选择。每笔允许的交易都会被检查，因此答案是正确的。
包含 n 个价格的列表大约有 n²/2 对：100,000 天意味着大约要进行 50 亿次减法。
算法
- 将
best设为 0。 - 遍历每个买入日
buy。 - 对于每个买入日，遍历其之后的每个卖出日
sell。 - 计算
prices[sell]减去prices[buy]的结果，如果结果更大，就将其存入best。 - 返回
best。
def maxProfit(prices):
best = 0
n = len(prices)
for buy in range(n):
for sell in range(buy + 1, n):
best = max(best, prices[sell] - prices[buy])
return best
一次遍历，记录目前为止的最低价格
思路
固定卖出日 i。最佳买入日是截至 i 的最低价日，因此在 i 卖出时，最佳交易收益是 prices[i] 减去目前为止的最低价格。每个卖出日都会与对应的最佳买入日配对，因此这些收益中的最大值就是答案。创下新低的当天，收益为 0，和不进行交易一样。
遍历过程中，每个价格只读取一次，并保留两个数值：lowest 和 best。时间复杂度为 O(n)，空间复杂度为 O(1)。
算法
- 将
lowest设为第一个价格，并将best设为 0。 - 按顺序遍历这些价格。
- 如果当前价格低于
lowest，就将它设为新的lowest。 - 计算当前价格减去
lowest的结果，如果结果更大，就将其存入best。 - 返回
best。
def maxProfit(prices):
lowest = prices[0]
best = 0
for price in prices:
if price < lowest:
lowest = price
elif price - lowest > best:
best = price - lowest
return best
易错点和边界情况
- 返回最高价格减去最低价格。在
[7, 2, 5, 9, 1, 4]中，结果是 8，但 1 出现在 9 之后。答案是 7。 - 让答案变成负数。在
[9, 7, 4, 3, 1]中，最佳差值是 -1；将best初始设为 0，而不是第一个差值。 - 将
lowest初始设为 0。这样每次利润都会等于价格本身，因此[9, 7, 4, 3, 1]会返回 9。将它初始设为第一个价格。
常见问题3
买卖股票的最佳时机的时间复杂度是多少？
对于 n 天，单次遍历的解法需要 O(n) 时间，因为它会读取每个价格一次；额外空间为 O(1)，用于保存目前为止的最低价格和最大利润。尝试每一对日期需要 O(n²) 时间。
为什么不从最高价格中减去最低价格？
最低价格可能出现在最高价格之后，而且你必须先买入再卖出。在 [7, 2, 5, 9, 1, 4] 中，1 出现在 9 之后，因此符合要求的最佳交易是在 2 时买入，在 9 时卖出，获利 7。
买卖股票的最佳时机是一道动态规划问题吗？
你可以用任一种方式理解它。迄今为止的最低价格是一小部分状态，你每天都会更新它，这就是动态规划的视角。将每次卖出与更早日期中的最低价格配对，就是贪心的视角。两种视角都会得到相同的单次遍历代码。
def maxProfit(prices):
# 在这里编写代码测试 #1
测试 #2
参数
prices = [7, 2, 5, 9, 1, 4]
预期输出
7