题目:121.买卖股票的最佳时机
给定一个数组 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:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
- 提示:
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
思路1
要计算在给定数组 prices
中获取的最大利润,你可以通过一次遍历解决问题。这个算法的关键是找到历史最低点和最大的利润差。具体步骤如下:
- 初始化一个变量
minPrice
为prices[0]
,表示历史最低价格。 - 初始化一个变量
maxProfit
为0
,表示当前最大的利润。 - 遍历价格数组,对于每个价格:
- 更新
minPrice
,即如果当前价格低于minPrice
,则更新minPrice
。 - 计算当前价格与
minPrice
的差值,即当前利润。如果当前利润大于maxProfit
,则更新maxProfit
。
- 更新
- 时间复杂度:O(n)
- 空间复杂度:O(1)
代码
public int maxProfit(int[] prices) {
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
// 更新历史最低价格
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
// 更新当前利润
int currentProfit = prices[i] - minPrice;
// 更新最大利润
if (currentProfit > maxProfit) {
maxProfit = currentProfit;
}
}
}
return maxProfit;
}
思路2
可以使用动态规划来解决这个问题。动态规划方法的核心思想是通过维护两个状态数组来跟踪买入和卖出的最大利润。在每一天,我们需要决定是否进行买入或卖出操作。
具体来说,我们定义两个数组 dp[i][0]
和 dp[i][1]
:
dp[i][0]
表示第i
天结束时持有现金的最大利润。dp[i][1]
表示第i
天结束时持有股票的最大利润。
状态转移方程
如果第
i
天持有现金,那么有两种可能:- 第
i-1
天也持有现金,则dp[i][0] = dp[i-1][0]
。 - 第
i-1
天持有股票,在第i
天卖出股票,则dp[i][0] = dp[i-1][1] + prices[i]
。
因此,dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i])
。
- 第
如果第
i
天持有股票,那么有两种可能:- 第
i-1
天也持有股票,则dp[i][1] = dp[i-1][1]
。 - 第
i-1
天持有现金,在第i
天买入股票,则dp[i][1] = -prices[i]
(注意:只允许交易一次,因此持有股票的最大利润就是当天的股价的相反数)。
因此,
dp[i][1] = Math.max(dp[i-1][1], -prices[i])
。- 第
时间复杂度:O(n)
空间复杂度:O(n)
代码
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][2];
// 0:持有现金
dp[0][0] = 0;
// 1:持有股票
dp[0][1] = -prices[0];
for (int i = 1; i < prices.length; i++) {
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[prices.length - 1][0];
}