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 股票问题完整体系。