【力扣100题】94.买卖股票的最佳时机
题目描述给定一个数组prices它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择某一天买入这只股票并选择在未来的某一个不同的日子卖出该股票。返回你能获取的最大利润。如果不能获取任何利润返回 0。示例 1输入[7,1,5,3,6,4] 输出5 解释在第 2 天买入价格1在第 5 天卖出价格6最大利润 6-1 5示例 2输入[7,6,4,3,1] 输出0 解释没有交易完成最大利润为 0解题思路总览思路时间复杂度空间复杂度适用场景暴力枚举O(n^2)O(1)能想到但会超时前缀最小值O(n)O(1)本题最优解动态规划O(n)O(n)通用解法算法一暴力枚举思路枚举所有可能的买入和卖出日期组合找到最大利润。代码classSolution{public:intmaxProfit(vectorintprices){intans0;intnprices.size();for(inti0;in;i){for(intji1;jn;j){ansmax(ans,prices[j]-prices[i]);}}returnans;}};算法流程输入: prices [7, 1, 5, 3, 6, 4] 第一层循环买入日 i ------------------------------------------------------------- | i0 (买入价7): | | j1: profit1-7-6 -- ans0 | | j2: profit5-7-2 -- ans0 | | ...全部负数 | ------------------------------------------------------------- | i1 (买入价1): | | j2: profit5-14 -- ans4 | | j3: profit3-12 -- ans4 | | j4: profit6-15 -- ans5 ★最大 | | j5: profit4-13 -- ans5 | ------------------------------------------------------------- | i2 (买入价5): ...全部负数 | ------------------------------------------------------------- 输出: ans 5复杂度分析复杂度分析时间复杂度O(n^2)- 两层循环枚举所有买卖组合空间复杂度O(1)算法二前缀最小值最优解思路遍历一次维护到当前位置为止的最低价格同时计算在最低价买入、今天卖出的利润。核心思想在每个位置 i我们想知道「之前最低多少钱买的」然后计算「今天卖能赚多少」。代码classSolution{public:intmaxProfit(vectorintprices){intans0;intmin_priceprices[0];for(intprice:prices){ansmax(ans,price-min_price);min_pricemin(price,min_price);}returnans;}};算法流程输入: prices [7, 1, 5, 3, 6, 4] 初始: min_price 7, ans 0 第一趟 (price7): ------------------------------------------------------------- | price7, min_price7 | | ans max(0, 7-7) 0 -- ans0 | | min_price min(7,7) 7 | ------------------------------------------------------------- 第二趟 (price1): ------------------------------------------------------------- | price1, min_price7 | | ans max(0, 1-7) 0 -- ans0 | | min_price min(7,1) 1 -- 更新最低价 | ------------------------------------------------------------- 第三趟 (price5): ------------------------------------------------------------- | price5, min_price1 | | ans max(0, 5-1) 4 -- ans4 | | min_price min(1,5) 1 | ------------------------------------------------------------- 第四趟 (price3): ------------------------------------------------------------- | price3, min_price1 | | ans max(4, 3-1) 4 -- ans4 | | min_price min(1,3) 1 | ------------------------------------------------------------- 第五趟 (price6): ------------------------------------------------------------- | price6, min_price1 | | ans max(4, 6-1) 5 -- ans5 ★最大 | | min_price min(1,6) 1 | ------------------------------------------------------------- 第六趟 (price4): ------------------------------------------------------------- | price4, min_price1 | | ans max(5, 4-1) 5 -- ans5 | | min_price min(1,4) 1 | ------------------------------------------------------------- 输出: ans 5复杂度分析复杂度分析时间复杂度O(n)- 只需一次遍历空间复杂度O(1)- 只用两个变量算法三动态规划思路定义dp[i]为以第 i 天结尾的最小买入价实际上就是前缀最小值也可以用dp[i]表示到第 i 天为止的最大利润。代码classSolution{public:intmaxProfit(vectorintprices){intnprices.size();if(n0)return0;// dp[i] 前 i 天的最低价格vectorintdp(n);dp[0]prices[0];intans0;for(inti1;in;i){dp[i]min(dp[i-1],prices[i]);ansmax(ans,prices[i]-dp[i]);}returnans;}};算法流程输入: prices [7, 1, 5, 3, 6, 4] 初始化: dp[0] 7, ans 0 i1: dp[1] min(7, 1) 1 ans max(0, 1-1) 0 i2: dp[2] min(1, 5) 1 ans max(0, 5-1) 4 i3: dp[3] min(1, 3) 1 ans max(4, 3-1) 4 i4: dp[4] min(1, 6) 1 ans max(4, 6-1) 5 i5: dp[5] min(1, 4) 1 ans max(5, 4-1) 5 输出: ans 5复杂度分析复杂度分析时间复杂度O(n)空间复杂度O(n)- dp 数组存储每个位置的前缀最小值复杂度对比总结思路平均时间最坏时间空间评价暴力枚举O(n^2)O(n^2)O(1)会超时前缀最小值O(n)O(n)O(1)最优动态规划O(n)O(n)O(n)可行但浪费空间前缀最小值核心思想prices [7, 1, 5, 3, 6, 4] 遍历过程 ------------------------------------------------------------- | 天数 | 价格 | 到此天的最低价 | 最大利润 | | | day0 | 7 | 7 | 0 | | | day1 | 1 | 1 ↓ | 0 | 更新最低 | | day2 | 5 | 1 | 4 ↑ | 赚4块 | | day3 | 3 | 1 | 4 | | | day4 | 6 | 1 | 5 ↑ | 赚5块 | | day5 | 4 | 1 | 5 | | ------------------------------------------------------------- 关键洞察在第 i 天卖出的最大利润 prices[i] - min(prices[0..i])面试追问 FAQ问题回答为什么只遍历一次因为买入必须在卖之前我们只需要记录「之前最低价」和「当前最大利润」如果 prices 为空怎么办题目保证 length 1不需要特判为什么不用动态规划数组前缀最小值只需要一个变量存历史最低用数组浪费空间如果想求具体哪两天买卖呢记录最低价出现的位置遍历时同步更新即可相关题目题目难度核心点122. 买卖股票的最佳时机 II中等允许多笔交易123. 买卖股票的最佳时机 III困难最多两笔交易188. 买卖股票的最佳时机 IV困难最多 k 笔交易121. 买卖股票的最佳时机简单单笔交易本题总结项目内容核心思想前缀最小值边遍历边记录历史最低价关键公式ans max(ans, price - min_price)最优时间O(n)最优空间O(1)面试加分能解释「在最低价买入、当前价卖出」的思想