LeetCode-热题100：121. 买卖股票的最佳时机

题目描述

给定一个数组 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。

提示：

• 1 <= prices.length <= 10⁵
• 0 <= prices[i] <= 10⁴

代码及解释

func maxProfit(prices []int) int {
    // 初始化最大利润为0
    res := 0
    // 初始化最低价格为第一天的价格
    minprice := prices[0]
    
    // 遍历价格数组
    for i := 0; i < len(prices); i++ {
        // 如果当前价格小于最低价格，更新最低价格
        if minprice > prices[i] {
            minprice = prices[i]
        } else {
            // 如果当前价格减去最低价格大于当前最大利润，更新最大利润
            res = max(res, prices[i] - minprice)
        }
    }
    // 返回最大利润
    return res
}

// 辅助函数，返回两个数中的较大值
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

代码解释

使用一种贪心算法来计算买卖股票的最大利润。

1. 初始化最大利润为0

   res := 0
   

   开始时，最大利润是0，因为在还没有进行任何交易之前，利润自然是0。

2. 初始化最低价格为第一天的价格

   minprice := prices[0]
   

   我们首先将最低价格设置为第一天的股票价格，这样在后续遍历价格时，可以比较当前价格与之前的最低价格，以找到更大的利润。

3. 遍历价格数组

   for i := 0; i < len(prices); i++ {
   

   我们遍历整个价格数组，尝试找到最低的买入价格并计算最大利润。

4. 如果当前价格小于最低价格，更新最低价格

   if minprice > prices[i] {
       minprice = prices[i]
   }
   

   在遍历过程中，如果我们找到一个更低的价格，我们就更新最低价格。这是为了确保我们买入股票时的价格是最低的。

5. 如果当前价格减去最低价格大于当前最大利润，更新最大利润

   res = max(res, prices[i] - minprice)
   

   如果当前价格减去最低价格能够给出一个更大的利润，我们就更新最大利润。这是因为我们在找到一个更低的买入价格后，可能会在之后的某一天卖出股票以获取更大的利润。

6. 返回最大利润

   return res
   

   最后，我们返回计算出的最大利润。

这个方法的关键在于：我们在遍历价格数组时，持续更新最低的买入价格，并计算每一天卖出股票可能获得的最大利润。这样，我们能够确保获得的利润是最大的。