算法练习第八天——买卖股票的最佳时机

算法练习第八天——买卖股票的最佳时机

买卖股票的最佳时机题目

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例一：

输入： prices = [7,6,5,4,3,2,1] 输出： 0 解释： 在这种情况下, 没有交易完成, 所以最大利润为 0。

示例二：

输入： prices = [7,2,4,3,1,9,8] 输出： 7 解释： 在第二天买入，第六天卖出，为最大利润7。

解题思路

方法一：一次遍历

我们只要用一个变量记录一个历史最低价格 minvalue，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minvalue。

因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

以下代码以golang为例：

func maxProfit(prices []int) int {
  minValue := math.MaxInt64
  maxValue := 0
  for i := 0; i < len(prices); i++ {
    if prices[i] < minValue {
      minValue = prices[i]
    } else if prices[i]-minValue > maxValue {
      maxValue = prices[i] - minValue
    }
  }
  return maxValue
}

该解法复杂度分析

• 时间复杂度：O(n)，需要遍历一次。

• 空间复杂度：O(1)，只使用了常数个变量。