LeetCode 121. 买卖股票的最佳时机

Categories:

Tags:

题目描述
思路分析
1. 解法一：一次遍历（记录最低价）（推荐）
2. 解法二：动态规划
相似题目

题目描述

✅ 121. 买卖股票的最佳时机

题目：

给定一个数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。只能选择某一天买入，并在未来某一不同日期卖出，求能获得的最大利润。若无法获得任何利润，返回 0。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：5
解释：第 2 天买入（价格=1），第 5 天卖出（价格=6），利润=6-1=5。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：价格持续下跌，无法盈利，最大利润为 0。

提示：

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

思路分析

解法一：一次遍历（记录最低价）（推荐）

核心思路：

维护历史最低价格 minPrice。

每天尝试以当前价格卖出，更新最大利润 maxProfit。

只允许一次交易，因此利润只与最低买入价相关。

复杂度分析：

时间复杂度：O(n)，其中 n 表示价格数组长度。

空间复杂度：O(1)，仅使用常数额外变量。

// 一次遍历记录最低价
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else {
                maxProfit = Math.max(maxProfit, price - minPrice);
            }
        }

        return maxProfit;
    }
}

// 一次遍历记录最低价
func maxProfit(prices []int) int {
	minPrice := int(^uint(0) >> 1)
	maxProfit := 0

	for _, price := range prices {
		if price < minPrice {
			minPrice = price
			continue
		}
		profit := price - minPrice
		if profit > maxProfit {
			maxProfit = profit
		}
	}

	return maxProfit
}

解法二：动态规划

核心思路：

定义 hold 表示持有股票时的最大收益，cash 表示不持有时的最大收益。

状态转移：

cash = max(cash, hold + price)

hold = max(hold, -price)

只允许一次交易，因此 hold 只能由 -price 转移。

复杂度分析：

时间复杂度：O(n)，其中 n 表示价格数组长度。

空间复杂度：O(1)，仅使用常数额外变量。

// 动态规划状态转移
class Solution {
    public int maxProfit(int[] prices) {
        int cash = 0;
        int hold = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];
            cash = Math.max(cash, hold + price);
            hold = Math.max(hold, -price);
        }

        return cash;
    }
}

// 动态规划状态转移
func maxProfit(prices []int) int {
	cash := 0
	hold := -prices[0]

	for i := 1; i < len(prices); i++ {
		price := prices[i]
		if hold+price > cash {
			cash = hold + price
		}
		if -price > hold {
			hold = -price
		}
	}

	return cash
}

相似题目

题目	难度	考察点
53. 最大子数组和	中等	动态规划
122. 买卖股票的最佳时机 II	中等	贪心
123. 买卖股票的最佳时机 III	困难	DP
188. 买卖股票的最佳时机 IV	困难	DP
309. 最佳买卖股票时机含冷冻期	中等	DP
1893. 检查是否区域内所有整数都被覆盖	简单	差分数组
2016. 增量元素之间的最大差值	简单	一次遍历
3531. 买卖股票的最佳时机 V	中等	DP
714. 买卖股票的最佳时机含手续费	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/60212631