题⽬描述

假设你有⼀个数组 prices，⻓度为 n，其中 prices[i] 是股票在第 i 天的价格，请根据这个价格数组，返回买卖股票能获得的最⼤收益

  1. 你可以买⼊⼀次股票和卖出⼀次股票，并⾮每天都可以买⼊或卖出⼀次，总共只能买⼊和卖出⼀次，且买⼊必须在卖出的前⾯的某⼀天

  2. 如果不能获取到任何利润，请返回 0

  3. 假设买⼊卖出均⽆⼿续费

示例1： 输⼊：[8,9,2,5,4,7,1] 返回值: 5 说明: 在第3天(股票价格 = 2)的时候买⼊，在第6天(股票价格 = 7)的时候卖出，最⼤利润 = 7-2 = 5，不能选择在第2天买⼊，第3天卖出，这样就亏损7了；同时，你也不能在买⼊前卖出股票。

示例2： 输⼊：[2,4,1] 返回值: 2

思路及解答

暴⼒穷举

这⾥涉及的节点⽆⾮是买⼊，卖出，那么我们遍历所有的数据，作为买⼊⽇期，同时将该⽇期后⾯每⼀个都作为卖出⽇期来计算，只要维护最⼤的利润即可。

  • 时间复杂度： O(n2)

  • 空间复杂度：O(1)

贪⼼法（最优解）

我们要想得到⼀个最⼤的利润，其实就是要两者差值最⼤。如果让差值最⼤，假设在当天卖出，那么什么时候买⼊最好呢？

当然是在前⾯找到最⼩的买⼊点，⽐如： ⽽前⾯的最⼩值，其实我们在遍历的时候是可以不断维护的，所以我们只要遍历⼀次数组即可。

关键思想：

  • 最大利润 = 某日价格 - 该日之前的最低价格

  • 只需维护两个变量：

    • minPrice：遍历过程中遇到的最低价格

    • maxProfit：当前能获得的最大利润

  • 时间复杂度：O(n)，只需遍历一次数组

  • 空间复杂度：O(1)，只使用常数空间

执行过程示例（prices = [8,9,2,5,4,7,1]）

动态规划

dp[i]表示前i天的最大利润，状态转移基于前i-1天的结果

状态定义：

  • minPrice[i]：前i天的最低价格

  • maxProfit[i]：前i天能获得的最大利润

  • 时间复杂度：O(n)，单次遍历

  • 空间复杂度：O(1)，优化后只需两个变量