考查应聘者的抽象建模能力。应聘者需要从股票买卖的特点入手总结出股票交易获得最大利润的条件。

Question

给定一个数组，它的第 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。

测试用例

功能测试（存储股票价格的数组无序、单调递增、单调递减）。 边界值测试（存储股票价格的数组中只有两个数字）。特殊输入测试（指向数组的指针为nullptr）。

本题考点

考查应聘者的抽象建模能力。应聘者需要从股票买卖的特点入手总结出股票交易获得最大利润的条件。 考查应聘者对数组的编程能力。

Intuition

我们先定义变量 curr_diff 为当卖出价为数组中第 i 个数字时可能获得的最大利润。 显然，在卖出价固定时，买入价越低获得的利润越大。 也就是说，如果在扫描到数组中的第 i 个数字时，只要我们能够记住之前的 i-1 个数字中的最小值，就能算出在当前价位卖出时可能得到的最大利润。我们用变量 _min 记录之前的 i-1 个数字中的最小值，用 max_diff 和 curr_diff 比较，然后记录获得的最大利润。

时间复杂度：\(O(n)\)； 空间复杂度：\(O(1)\)。

Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if length < 2:
            return 0
        _min = prices[0] 
        max_diff = prices[1] - _min
        for i in range(2, length):
            if prices[i-1] < _min:
                _min = prices[i-1]
            curr_diff = prices[i] - _min
            if curr_diff > max_diff:
                max_diff = curr_diff
        # 特判股价一直下跌的情况，max_diff可能为负。
        return max_diff if max_diff > 0 else 0

Extension

LeetCode 股票问题的一种通用解法