7.买卖股票的最佳时机
题目
给定一个数组prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。
示例 1:
- 输入：[7,1,5,3,6,4]
- 输出：5
-
解释：在第2天（股票价格 = 1）的时候买入，在第5天（股票价格=6）的时候卖出，最大利润=
6-1 = 5。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2: -
输入：prices = [7,6,4,3,1]
- 输出：0
- 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
思路
暴力遍历
先考虑最简单的「暴力遍历」，即枚举出所有情况，并从中选择最大利润。设数组 prices 的长度为 n ，由于只能先买入后卖出，因此第 1 天买可在未来 n−1 天卖出，第 2 天买可在未来 n−2 天卖出……以此类推，要思考更优解法。
然而，暴力法会产生许多冗余计算。例如，若第 1 天价格低于第 2 天价格，即第 1 天成本更低，那么我们一定不会选择在第 2 天买入。进一步的，若在前 i 天选择买入，若想达到最高利润，则一定选择价格最低的交易日买入。
贪心思想
考虑根据此贪心思想，遍历价格列表 prices 并执行两步：
- 更新前 i 天的最低价格，即最低买入成本 cost；
- 更新前 i 天的最高利润 profit ，即选择「前 i−1 天最高利润 profit 」和「第 i 天卖出的最高利润 price - cost 」中的最大值 ；
class Solution:
def maxProfit(self, prices: List[int]) -> int:
minPrice = prices[0]
cost = 0
for i in prices:
if i < minPrice:
minPrice = i
elif i - minPrice > cost:
cost = i - minPrice
return cost
- 邮箱 ：charon.chui@gmail.com
- Good Luck!