“陌陌”推荐算法面试题，股票最大利润，并且输出买卖价格

轩辕小不懂发布于 2021-09-16 15:08

阅读 573

答案 1

分类：面试与就业

Nen 2021-09-16 15:14

- 程序员

方法一:暴力解法

对数组进行遍历，找到后一个数与前一个数的最大差值，返回。注意遍历j时要从i+1进行遍历。

代码如下：

class Solution

defmaxProfit(self，prices：List[int]）->int

res=0

fori in range(len(prices））：

forjinrange(i+l,len(prices））

res=max(res,prices[j]-pricesti]）

return res

方法二：

只进行一次遍历，在遍历过程中更新两个值，股票最小值和差值最大值，更新到最后即可。

代码如下：

class Solution:

defmaxProfit(self，prices:List[int]）->int

res=0

minPrice = pricesO]

fori inrange(len(prices））：

res=max(res，prices[i]-minPrice）

minPrice=min(minPrice，pricesLi]）

return res

时间复杂度：O(n)

空间复杂度：O(1)