LeetCode 121. 买卖股票的最佳时机（C语言详解 | 贪心算法）

一、题目描述

给定一个数组 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

解释：

价格一直下降，没有盈利机会

二、题目分析

题目的关键限制：

必须先买，再卖

所以不能简单：

最大值 – 最小值

例如：

[7,6,4,3,1]

最大值 = 7
最小值 = 1

但 7 在 1 前面，不能先买1再卖7。

三、核心思路（贪心算法）

我们在遍历数组时维护两个变量：

minPrice ：历史最低价格
maxProfit ：最大利润

遍历每一天：

1 计算今天卖出的利润

profit = prices[i] – minPrice

2 更新最大利润

maxProfit = max(maxProfit, profit)

3 更新最低价格

minPrice = min(minPrice, prices[i])

四、图解过程

数组：

[7,1,5,3,6,4]

遍历过程：

最终结果：

maxProfit = 5

五、C语言实现

int maxProfit(int* prices, int pricesSize) {
if (pricesSize == 0) {
return 0;
}

int minPrice = prices[0];
int maxProfit = 0;

for (int i = 1; i < pricesSize; i++) {

// 计算今天卖出的利润
int profit = prices[i] – minPrice;

if (profit > maxProfit) {
maxProfit = profit;
}

// 更新历史最低价格
if (prices[i] < minPrice) {
minPrice = prices[i];
}
}

return maxProfit;
}

六、复杂度分析

时间复杂度

O(n)

只遍历一次数组。

空间复杂度

O(1)

只使用常数变量。

七、优化思路（动态规划角度）

其实也可以理解为 动态规划问题。

定义：

dp[i] = 第 i 天卖出股票能获得的最大利润

但由于只依赖：

历史最低价格

所以可以将 DP 压缩成两个变量：

minPrice
maxProfit

因此最终代码只需要 O(1) 空间。

八、总结

本题核心思想只有一句话：

遍历数组时记录历史最低价格，并尝试在当前价格卖出，更新最大利润。

步骤：

1️⃣ 记录历史最低价
2️⃣ 计算当前卖出利润
3️⃣ 更新最大利润

九、相关题目

股票系列题目（LeetCode经典）：

建议顺序：

121 → 122 → 309 → 714 → 123 → 188

这是 LeetCode 股票问题完整体系。