0121.md

title	description	keywords
121. 买卖股票的最佳时机	LeetCode 121. 买卖股票的最佳时机题解，Best Time to Buy and Sell Stock，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 121. 买卖股票的最佳时机 买卖股票的最佳时机 Best Time to Buy and Sell Stock 解题思路 数组 动态规划

121. 买卖股票的最佳时机

🟢 Easy  🔖  数组 动态规划  🔗 力扣 LeetCode

题目

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]

Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]

Output: 0

Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

题目大意

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]

输出：5

解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]

输出：0

解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

解题思路

思路一：动态规划

1. **动态规划：**定义一个二维数组 dp，其中 dp[i][0] 表示第 i 天不持有股票时的最大利润， dp[i][1] 表示第 i 天持有股票时的最大利润。

2. 状态转移方程：

   • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])，表示在第 i 天，不持有股票的最大利润等于前一天不持有股票的最大利润，或者前一天持有股票的最大利润加上今天卖出的利润的最大值。
   • dp[i][1] = max(dp[i-1][1], -prices[i])，表示在第 i 天，持有股票的最大利润等于前一天持有股票的最大利润，或者前一天不持有股票的最大利润减去今天买入的利润的最大值。由于题目规定只能买入一次，所以前一天不持有股票的最大利润为 0。

3. **边界条件：**第一天（i == 0）时，dp[0][0] = 0，dp[0][1] = -prices[0]。

4. **初始化：**初始化利润为 0。

5. **返回最大利润：**最后返回 dp[n - 1][0]，即最后一天不持有股票的最大利润，因为若最后一天还持有股票没有卖出，收益肯定小于做了一次交易的情况。

复杂度分析

• 时间复杂度: O(n)，其中 n 是股票价格数组的长度，遍历了整个数组。
• 空间复杂度: O(n)，使用了一个 2 * n 的二维数组来存储中间状态。

---

思路二：动态规划-状态压缩

根据上面的代码可以发现，dp[i][...] 只与 dp[i - 1][0]、dp[i - 1][1] 有关。

因此不需要使用整个 dp 数组，只需用两个变量储存这两个状态就足够了，这样可以把空间复杂度降到 O(1)：

• min_price 记录当前位置之前的最低股价
• max_profit 记录最大利润。

1. 遍历数组： 从头到尾遍历股票价格数组。

2. 维护最低价格： 在遍历的过程中，维护一个变量，记录当前位置之前的最低股价。

3. 更新最大利润： 对于每一天，计算当前股价与最低价格的差值，如果大于之前的最大利润，更新最大利润。

4. 返回最大利润： 遍历完成后，返回最大利润。

复杂度分析

• 时间复杂度: O(n)，其中 n 是股票价格数组的长度，遍历了整个数组。
• 空间复杂度: O(1)，使用了常数个变量来存储中间状态。

代码

::: code-tabs @tab 动态规划

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
	const n = prices.length;
	const dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
	for (let i = 0; i < n; i++) {
		if (i == 0) {
			dp[0][0] = 0;
			dp[0][1] = -prices[0];
			continue;
		}
		dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
		dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
	}
	return dp[n - 1][0];
};

@tab 动态规划-状态压缩

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
	let min_price = prices[0];
	let max_profit = 0;
	for (let price of prices) {
		min_price = Math.min(min_price, price);
		max_profit = Math.max(max_profit, price - min_price);
	}
	return max_profit;
};

:::

相关题目

题号	标题	题解	标签	难度	力扣
53	最大子数组和	[✓]	数组 分治 动态规划	🟠	🀄️ 🔗
122	买卖股票的最佳时机 II	[✓]	贪心 数组 动态规划	🟠	🀄️ 🔗
123	买卖股票的最佳时机 III	[✓]	数组 动态规划	🔴	🀄️ 🔗
188	买卖股票的最佳时机 IV	[✓]	数组 动态规划	🔴	🀄️ 🔗
309	买卖股票的最佳时机含冷冻期	[✓]	数组 动态规划	🟠	🀄️ 🔗
2012	数组美丽值求和		数组	🟠	🀄️ 🔗
2016	增量元素之间的最大差值	[✓]	数组	🟢	🀄️ 🔗
2291	最大股票收益 🔒		数组 动态规划	🟠	🀄️ 🔗