AcWing 83.股票的最大利润（Python版）

题目描述

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖 一次 该股票可能获得的利润是多少？

例如一只股票在某些时间节点的价格为[9, 11, 8, 5, 7, 12, 16, 14]。

如果我们能在价格为5的时候买入并在价格为16时卖出，则能收获最大的利润11。 样例：

解题思路

1、首先想到暴力法 每一个元素都当做最低价，往后遍历找到最高差价，时间复杂度O（n^2），LeetCode上无法通过 2、一次遍历法 用一个变量记录遍历过的元素中的最低价，寻找当前价与最低价之间的最高差价：即在遍历过程中如果有比最低价更低的价格，则更新最低价，同时更新最高差价即最大利润

代码实现

class Solution(object): def maxDiff(self, nums): """ :type nums: List[int] :rtype: int """ if not nums: return 0 profit = 0 min_price = nums[0] # 把第一个价格当做最低价 for i in nums[1:]: if i < min_price: # 在遍历过程中更新最低价 min_price = i elif i > min_price: # 更新最大利润 temp = i - min_price profit = max(profit, temp) return profit