题目描述
给定一个数组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(vector<int>&prices){intans=0;intn=prices.size();for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){ans=max(ans,prices[j]-prices[i]);}}returnans;}};
算法流程
输入: prices = [7, 1, 5, 3, 6, 4] 第一层循环（买入日 i）： +-------------------------------------------------------------+ | i=0 (买入价=7): | | j=1: profit=1-7=-6 --> ans=0 | | j=2: profit=5-7=-2 --> ans=0 | | ...全部负数 | +-------------------------------------------------------------+ | i=1 (买入价=1): | | j=2: profit=5-1=4 --> ans=4 | | j=3: profit=3-1=2 --> ans=4 | | j=4: profit=6-1=5 --> ans=5 ★最大 | | j=5: profit=4-1=3 --> ans=5 | +-------------------------------------------------------------+ | i=2 (买入价=5): ...全部负数 | +-------------------------------------------------------------+ 输出: ans = 5
复杂度分析
| 复杂度 | 分析 |
|---|
| 时间复杂度 | O(n^2) |
| - 两层循环枚举所有买卖组合 |
| 空间复杂度 | O(1) |
算法二：前缀最小值（最优解）
思路
遍历一次，维护到当前位置为止的最低价格，同时计算在最低价买入、今天卖出的利润。
核心思想：在每个位置 i，我们想知道「之前最低多少钱买的」，然后计算「今天卖能赚多少」。
代码
classSolution{public:intmaxProfit(vector<int>&prices){intans=0;intmin_price=prices[0];for(intprice:prices){ans=max(ans,price-min_price);min_price=min(price,min_price);}returnans;}};
算法流程
输入: prices = [7, 1, 5, 3, 6, 4] 初始: min_price = 7, ans = 0 第一趟 (price=7): +-------------------------------------------------------------+ | price=7, min_price=7 | | ans = max(0, 7-7) = 0 --> ans=0 | | min_price = min(7,7) = 7 | +-------------------------------------------------------------+ 第二趟 (price=1): +-------------------------------------------------------------+ | price=1, min_price=7 | | ans = max(0, 1-7) = 0 --> ans=0 | | min_price = min(7,1) = 1 <-- 更新最低价 | +-------------------------------------------------------------+ 第三趟 (price=5): +-------------------------------------------------------------+ | price=5, min_price=1 | | ans = max(0, 5-1) = 4 --> ans=4 | | min_price = min(1,5) = 1 | +-------------------------------------------------------------+ 第四趟 (price=3): +-------------------------------------------------------------+ | price=3, min_price=1 | | ans = max(4, 3-1) = 4 --> ans=4 | | min_price = min(1,3) = 1 | +-------------------------------------------------------------+ 第五趟 (price=6): +-------------------------------------------------------------+ | price=6, min_price=1 | | ans = max(4, 6-1) = 5 --> ans=5 ★最大 | | min_price = min(1,6) = 1 | +-------------------------------------------------------------+ 第六趟 (price=4): +-------------------------------------------------------------+ | price=4, min_price=1 | | ans = max(5, 4-1) = 5 --> ans=5 | | min_price = min(1,4) = 1 | +-------------------------------------------------------------+ 输出: ans = 5
复杂度分析
| 复杂度 | 分析 |
|---|
| 时间复杂度 | O(n) |
| - 只需一次遍历 |
| 空间复杂度 | O(1) |
| - 只用两个变量 |
算法三：动态规划
思路
定义dp[i]为以第 i 天结尾的最小买入价（实际上就是前缀最小值），也可以用dp[i]表示到第 i 天为止的最大利润。
代码
classSolution{public:intmaxProfit(vector<int>&prices){intn=prices.size();if(n==0)return0;// dp[i] = 前 i 天的最低价格vector<int>dp(n);dp[0]=prices[0];intans=0;for(inti=1;i<n;i++){dp[i]=min(dp[i-1],prices[i]);ans=max(ans,prices[i]-dp[i]);}returnans;}};
算法流程
输入: prices = [7, 1, 5, 3, 6, 4] 初始化: dp[0] = 7, ans = 0 i=1: dp[1] = min(7, 1) = 1 ans = max(0, 1-1) = 0 i=2: dp[2] = min(1, 5) = 1 ans = max(0, 5-1) = 4 i=3: dp[3] = min(1, 3) = 1 ans = max(4, 3-1) = 4 i=4: dp[4] = min(1, 6) = 1 ans = max(4, 6-1) = 5 i=5: 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) |
| 面试加分 | 能解释「在最低价买入、当前价卖出」的思想 |
