在求解最佳买卖股票时间时，max()arg是一个空序列

Question

我正在处理一个名为"最佳买卖股票时间"；。

您将得到一个数组prices，其中prices[i]是给定股票在i天的价格。

你想通过选择一天购买一只股票，并在未来选择另一天出售该股票来实现利润最大化。

返回您可以从该交易中获得的最大利润。如果您无法获得任何利润，请返回0。

限制：

1 <= prices.length <= 10**5

0 <= prices[i] <= 10**4

这是我的解决方案：

class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = []
for i in range(len(prices)):
for j in range(i+1,len(prices)):
res.append(prices[j] - prices[i])
if max(res) <= 0:
return 0
else:
return max(res)

我在IDE(VS代码(上测试了所有的案例，结果都通过了。但是，当我在LeetCode上提交它时，我得到了如下所示的错误。我的代码出了什么问题？

ValueError: max() arg is an empty sequence
if max(res) <= 0:

Answer 1

LeetCode告诉您价格的约束是：

1 <= prices.length <= 10**5

如果是prices.length == 1，那么for循环的内部将永远不会激发，从而导致res为空列表。

一个解决方案是在你的功能顶部添加一个if保护，因为如果只有一天可以买卖，你就不能在另一天卖出股票：

def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 1:
return 0

---

然而，运行时是prices列表长度的二次方，并且最多需要考虑10**5天，即使添加了if保护，您的方法也会超时。

这是一种线性时间方法：基本上，对于每一天，你都想计算当天之前看到的最便宜的股价和当天之后看到的最贵的股价。这允许您只考虑可行的买卖可能性(即，它们满足在出售股票之前必须购买股票的限制。(以下代码将通过LeetCode的测试用例。

import math
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_prices = [0] * len(prices)
max_prices = [0] * len(prices)

min_price = math.inf
max_price = 0
for i in range(len(prices)):
min_price = min(min_price, prices[i])
min_prices[i] = min_price

for i in range(len(prices) - 1, -1, -1):
max_price = max(max_price, prices[i])
max_prices[i] = max_price

result = 0
for minimum, maximum in zip(min_prices, max_prices):
result = max(maximum - minimum, result)
return result