剑指 Offer 面试题 63「股票的最大利润」：一次遍历求最大利润的贪心/动态规划详解（doocs/leetcode 多语言题解）

• 示例工程

本篇技术指南围绕《剑指 Offer（第 2 版）》面试题 63「股票的最大利润」展开，它是 LeetCode 主站第 121 题「Best Time to Buy and Sell Stock」的同题版本，也是买卖股票系列中最基础、最常被面试官考察的动态规划入门题。本文以 doocs/leetcode 仓库中该题的 README 文档 为骨架，结合仓库内 Python3、Java、C++、Go、TypeScript、Rust、JavaScript、C#、Swift 共 9 种语言的 Solution 实现，完整讲解一次遍历求解思路、边界情况处理与复杂度分析，读者读完后可直接掌握该类"区间最优买卖"问题的通用解法，并对照仓库源码加深理解。

题目描述

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1：

输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。 注意利润不能是 7-1 = 6，因为卖出价格需要大于买入价格。

示例 2：

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下，没有交易完成，所以最大利润为 0。

限制：

0 <= 数组长度 <= 10^5

注意：本题与主站第 121 题相同，属于买卖股票系列（Best Time to Buy and Sell Stock）中最基础的"只能交易一次"模型。

题意分析与核心思路

先明确三个关键约束，它们直接决定了算法的形态：

1. 只能买卖一次：买入必须发生在卖出之前（先买后卖），买入日是卖出日之前的某一天；
2. 价格数组按时间排序：prices[i]表示第i+1天的价格，下标即时间轴；
3. 无交易也算合法结果：当所有天价格单调递减时，任何"先买后卖"都会亏损，此时最优策略是不交易，最大利润为0（这正是示例 2 的情况）。

基于这些约束，一个直观但低效的做法是枚举所有"买入日 + 卖出日"对（平方级），不可取。注意到一个关键观察：固定某一天作为卖出日时，要使利润最大，买入日必然是这一天之前价格最低的那一天。也就是说，对每个下标i，若记录i之前（含i之前所有天）出现的最低价格mi，则"在第i天卖出"可获得的最大利润为prices[i] - mi；全局答案就是所有这样的利润取最大值。

这个思路把"枚举买卖日对"降维成"枚举卖出日 + 维护历史最低买入价"，只需从左到右扫描一遍数组，这正是本题的标准解法。

方法一：一次遍历维护最低价与最大利润

算法流程

• 初始化变量mi为"历史最低价格"，初始值应为一个足够大的数（如正无穷），保证第一次计算x - mi不会产生错误结果；
• 初始化答案变量ans = 0，对应"不交易"这一保底选择；
• 从左到右遍历价格数组prices：
  1. 用当前价格x更新答案：ans = max(ans, x - mi)，即以x为卖出价、此前最低价mi为买入价得到的利润；
  2. 用当前价格x更新历史最低价：mi = min(mi, x)，为后续天数的卖出做铺垫。

循环结束后ans即为最大利润。由于初始化ans = 0，即使全程价格单调递减（示例 2 的[7,6,4,3,1]），x - mi始终为负，ans保持为0，天然覆盖了"不交易"的情况，无需额外分支判断。

复杂度分析

• 时间复杂度 O(n)：只需一次线性扫描，n为数组prices的长度；
• 空间复杂度 O(1)：仅使用两个常数级别的变量mi与ans。

在0 <= 数组长度 <= 10^5的限制下，该解法可以轻松通过。

正确性论证

假设全局最优交易为"第b天买入、第s天卖出"（b < s），那么在第s天被扫描到时，mi一定不大于prices[b]（因为b < s，prices[b]已经被纳入mi的更新范围），于是prices[s] - mi >= prices[s] - prices[b]，即扫描到第s天时计算出的候选利润不会小于全局最优利润。而ans会取所有候选利润的最大值，因此ans必然不小于全局最优利润；另一方面，任何候选利润x - mi都对应一个合法的"此前某天买入、当天卖出"交易，不会超过全局最优利润。两者结合即得ans恰好等于最大利润。

多语言实现

仓库在 lcof/面试题63. 股票的最大利润/ 目录下为本题提供了 9 种语言的独立可运行实现，逻辑完全一致：mi（或min）维护历史最低价，ans（或res）维护最大利润。各语言的具体差异主要体现在"无穷大/极大值"的表示方式上：

• Python3：使用inf表示正无穷；
• Java / C++ / Go / JavaScript / C#：使用1 << 30（即 2^30，约 10.7 亿）作为足够大的初始值。由于题目限制数组长度最大 10^5 且股价为常规整数，1 << 30远大于任何可能的价格差，可作为"虚拟正无穷"；
• TypeScript / Rust / Swift：分别使用Infinity、i32::MAX、Int.max作为语言内的最大值表示。

Python3

完整实现见 Solution.py：

class Solution: def maxProfit(self, prices: List[int]) -> int: mi, ans = inf, 0 for x in prices: ans = max(ans, x - mi) mi = min(mi, x) return ans

Java

完整实现见 Solution.java：

class Solution { public int maxProfit(int[] prices) { int mi = 1 << 30, ans = 0; for (int x : prices) { ans = Math.max(ans, x - mi); mi = Math.min(mi, x); } return ans; } }

C++

完整实现见 Solution.cpp：

class Solution { public: int maxProfit(vector<int>& prices) { int mi = 1 << 30, ans = 0; for (int& x : prices) { ans = max(ans, x - mi); mi = min(mi, x); } return ans; } };

Go

完整实现见 Solution.go。这里使用了 Go 内置泛型函数max/min（需 Go 1.21+），并利用命名返回值(ans int)在函数末尾直接return：

func maxProfit(prices []int) (ans int) { mi := 1 << 30 for _, x := range prices { ans = max(ans, x-mi) mi = min(mi, x) } return }

TypeScript

完整实现见 Solution.ts：

function maxProfit(prices: number[]): number { let res = 0; let min = Infinity; for (const price of prices) { res = Math.max(res, price - min); min = Math.min(min, price); } return res; }

Rust

完整实现见 Solution.rs：

impl Solution { pub fn max_profit(prices: Vec<i32>) -> i32 { let mut res = 0; let mut min = i32::MAX; for price in prices { res = res.max(price - min); min = min.min(price); } res } }

JavaScript

完整实现见 Solution.js：

/** * @param {number[]} prices * @return {number} */ var maxProfit = function (prices) { let mi = 1 << 30; let ans = 0; for (const x of prices) { ans = Math.max(ans, x - mi); mi = Math.min(mi, x); } return ans; };

C#

完整实现见 Solution.cs：

public class Solution { public int MaxProfit(int[] prices) { int mi = 1 << 30; int ans = 0; foreach(int x in prices) { ans = Math.Max(ans, x - mi); mi = Math.Min(mi, x); } return ans; } }

Swift

完整实现见 Solution.swift：

class Solution { func maxProfit(_ prices: [Int]) -> Int { var mi = Int.max var ans = 0 for x in prices { ans = max(ans, x - mi) mi = min(mi, x) } return ans } }

边界情况与易错点

对照两个官方示例与限制条件，重点注意以下细节：

1. 空数组：数组长度的下限为0。当prices为空时，循环体一次都不执行，ans保持初始值0，直接返回，无需额外判空；
2. 严格递减序列（如[7,6,4,3,1]）：所有x - mi均为负数，但ans初始化为0保证了"不交易"这一最优选择被正确返回，不能把ans初始化为-inf或某一天的价格，否则空数组/全跌场景会得到错误答案；
3. 先更新 ans 还是先更新 mi 的顺序：必须先计算x - mi（用旧的最低买入价），再执行mi = min(mi, x)。若顺序颠倒，x被先写入mi，则x - mi恒为 0，会丢失"当天之前的最低价买入"这一信息——虽然本题结果不受影响（因为可以当天买卖不产生利润，等价于不交易），但语义上不正确，且在其他变体题中会引入错误；
4. mi初始值的选取：Java/C++/Go/JavaScript/C# 中1 << 30是足够大的安全初值；Python 用inf、Rust 用i32::MAX、Swift 用Int.max、TypeScript 用Infinity，均保证第一次x - mi计算不会产生异常值。

与主站 121 题及买卖股票系列的关系

本题在《剑指 Offer》中是第 63 题，与 LeetCode 主站第 121 题（Best Time to Buy and Sell Stock）完全相同，仓库 lcof/lcof.json 中该题（ID 100344）的元数据也将其标记为「动态规划」（Dynamic Programming）、难度「中等」，归属于lcof（剑指 Offer）分类。

这一题是整个买卖股票系列的第一环，系列后续题目在它基础上逐步增加约束，解题思路随之升级：

• 只能交易一次（本题 / 121 题）：一次遍历维护最低价，O(n) 时间、O(1) 空间；
• 可以交易多次（122 题）：累计所有"上涨段"的差价，贪心即可；
• 最多交易两次（123 题）、最多交易 k 次（188 题）：引入二维状态动态规划；
• 含冷冻期（309 题）、含手续费（714 题）：在状态转移中加入冷冻/费用的维度。

从源码结构看，doocs/leetcode 仓库在 solution 目录下按题号区间维护了主站题解（如 solution/0100-0199），而 lcof、lcci、lcof2、lcp 等目录分别对应剑指 Offer、程序员面试金典、剑指 Offer 专项突击版与 LCP 系列，同一算法模型在不同题集间互相印证，非常适合对照学习。

总结

「股票的最大利润」虽然被标记为动态规划类题目，但其最优解本质上是一趟线性扫描：用mi记录历史最低买入价、用ans记录截至当前的最高利润，两者交替更新即可在 O(n) 时间内得到答案，空间开销为 O(1)。理解"固定卖出日、最优买入即此前最低价"这一核心观察，是掌握本题乃至整个买卖股票系列的关键。仓库为该题提供的 README 题解 与 9 种语言实现（Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs、Solution.swift）可直接作为刷题与面试准备时的参考模板。

• 示例工程