股票买卖的最佳时机问题 题目描述 给定一个数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。请设计算法计算通过一次买卖交易（即先买入后卖出）能获得的最大利润。注意：不能在买入前卖出，且只能完成一次交易。 示例 输入： prices = [7,1,5,3,6,4] 输出： 5 解释：在第 2 天买入（价格 = 1），在第 5 天卖出（价格 = 6），利润 = 6-1 = 5。 解题过程 步骤 1：暴力解法（理解问题本质） 最直观的方法是枚举所有可能的买卖组合，即对于每一天 i 作为买入日，遍历其后的每一天 j 作为卖出日，计算利润 prices[j] - prices[i] ，并记录最大值。 时间复杂度：O(n²)，会超时。 核心问题：重复计算了卖出日的比较过程。 步骤 2：动态规划思路 定义状态 dp[i] 表示前 i 天中的最低价格（即最低买入成本）。则第 i 天卖出的最大利润为 prices[i] - dp[i-1] 。 状态转移： dp[i] = min(dp[i-1], prices[i]) 最大利润： max_profit = max(max_profit, prices[i] - dp[i-1]) 优化：由于 dp[i] 只依赖前一个状态，可压缩为变量 min_price 。 步骤 3：一次遍历的贪心策略 初始化 min_price 为第一天的价格， max_profit = 0 。 遍历每一天的价格 p ： 更新 min_price = min(min_price, p) （记录历史最低价）。 计算当前卖出利润 p - min_price ，并更新 max_profit 。 返回 max_profit 。 举例说明 以 prices = [7,1,5,3,6,4] 为例： 第 1 天： min_price=7 ，利润=0。 第 2 天： min_price=1 ，利润=0。 第 3 天： min_price=1 ，利润=4 → max_profit=4 。 第 4 天： min_price=1 ，利润=2。 第 5 天： min_price=1 ，利润=5 → max_profit=5 。 第 6 天： min_price=1 ，利润=3。 复杂度分析 时间复杂度：O(n)，只需一次遍历。 空间复杂度：O(1)，仅用常数变量。 关键点 本质是找到历史最低点与后续最高点的最大差值。 贪心策略通过维护历史最小值，避免重复比较。