算法题

昨天晚上十一点多,我在公司楼下买可乐,我们组那个小刘突然拦住我:哥,这道Best Time to Buy and Sell Stock咋写啊,我脑壳疼。

我扫了一眼代码,心想这题挺经典的,来,我给你捋一捋。

##算法题：Best Time to Buy and Sell Stock

题目理解

题目说给你一个数组 prices,prices[i] 是第 i 天的股票价格。

你最多只能完成一笔交易,也就是只能买一次卖一次。

设计算法计算你能获取的最大利润。

注意不能在买入前卖出,也就是买入日期必须在卖出日期之前。

举例说明:

• 输入 [7,1,5,3,6,4],输出 5。第2天买入(价格1),第5天卖出(价格6),利润5
• 输入 [7,6,4,3,1],输出 0。价格一直在跌,不买最合适

说白了就是:找一个最低的买入价和一个最高的卖出价,让它们的差最大。

思路分析

暴力解法:枚举所有可能的买入卖出组合,计算利润,取最大值。两重循环,时间复杂度 O(n²),空间复杂度 O(1)。n=10000时就是一亿次操作,肯定会超时。

优化思路 - 一次遍历:维护两个变量,minPrice(历史最低价格)和maxProfit(历史最大利润)。遍历数组,每次计算当前价格减minPrice,如果比maxProfit大就更新。同时更新minPrice。时间复杂度 O(n),空间复杂度 O(1)。

核心思想是:我们要找到最低的买入价,后面的价格中哪个减去它最大,这就是最大利润。

复杂度分析

• 时间复杂度:O(n),其中 n 是数组长度
• 空间复杂度:O(1),只用常数空间

代码实现

package main

import (
 "fmt"
)

// maxProfit 计算买卖股票的最大利润
func maxProfit(prices []int) int {
 if len(prices) < 2 {
  return 0
 }

 minPrice := prices[0]
 maxProfit := 0

 for i := 1; i < len(prices); i++ {
  // 计算如果今天卖出能赚多少
  currentProfit := prices[i] - minPrice
  if currentProfit > maxProfit {
   maxProfit = currentProfit
  }
  // 更新历史最低价格
  if prices[i] < minPrice {
   minPrice = prices[i]
  }
 }

 return maxProfit
}

func main() {
 // 测试用例
 fmt.Println(maxProfit([]int{7, 1, 5, 3, 6, 4}))  // 5
 fmt.Println(maxProfit([]int{7, 6, 4, 3, 1}))     // 0
 fmt.Println(maxProfit([]int{1, 2}))             // 1
 fmt.Println(maxProfit([]int{2, 4, 1}))          // 2
 fmt.Println(maxProfit([]int{3, 3, 5, 0, 0, 3, 1, 4}))  // 4
}

注意事项

• 边界条件:数组长度小于2,无法买卖,直接返回0。价格一直在跌,最大利润就是0,不能为负数。
• 一次交易:题目说最多只允许完成一笔交易,所以只能买一次卖一次。不能买卖多次,这是关键点。
• 买入卖出顺序:买入日期必须在卖出日期之前,不能先卖后买。所以遍历时要确保卖出价在买入价后面。
• 整数溢出:如果价格和利润都很大,可能会溢出。但题目一般限制在int范围内,Go的int足够大。
• 利润为负数:如果价格一直在跌,最大利润就是0,不买股票。代码中maxProfit初始化为0就处理了这种情况。

这题的关键点在于理解一次遍历的思路。我们要找最低的买入价和最高的卖出价,但不能简单找最小值和最大值,因为买入必须在卖出之前。所以要用一次遍历,维护历史最低价,同时计算每次卖出的利润。