leetcode
leetcode 2601 ~ 2650
买卖芯片的最佳时机

买卖芯片的最佳时机

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 44 ms, 内存: 17.8 MB


/*
 * 思路:
 * 使用Java Stream来实现上述逻辑。
 * 我们可以使用一个自定义的类来在流中传递当前的最低价格和最大利润。
 */
import java.util.stream.IntStream;

public class Solution {
    public int maxProfit(int[] prices) {
        class State {
            int minPrice = Integer.MAX_VALUE;
            int maxProfit = 0;
        }

        State state = new State();

        IntStream.of(prices).forEach(price -> {
            state.minPrice = Math.min(state.minPrice, price);
            state.maxProfit = Math.max(state.maxProfit, price - state.minPrice);
        });

        return state.maxProfit;
    }
}

解释

方法:

这个题解使用了动态规划的思想来解决问题。我们定义 dp[i][0] 为第 i 天结束时不持有股票所能获得的最大利润,而 dp[i][1] 为第 i 天结束时持有股票所能获得的最大利润。状态转移方程如下:dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]) 表示第 i 天不持有股票的情况下,可以是前一天也不持有,或者是前一天持有但在今天卖出。dp[i][1] = max(dp[i-1][1], -prices[i-1]) 表示第 i 天持有股票的情况下,可以是前一天持有,或者是今天新买入股票。

时间复杂度:

O(n)

空间复杂度:

O(n),但可优化至 O(1)

代码细节讲解

🦆
为什么在定义`dp[i][1]`时使用`-prices[i-1]`而不是`prices[i-1]`?这样的定义是如何体现买入芯片的成本的?
在动态规划中,`dp[i][1]`代表在第 i 天结束时持有股票所能获得的最大利润。当选择在第 i 天买入股票时,我们必须支付芯片的价格 `prices[i-1]`(因为数组下标从0开始,所以第i天的价格是`prices[i-1]`),这意味着我们的现金会减少。因此,我们使用 `-prices[i-1]` 来更新状态,表示这一天买入股票后的负成本(即现金减少)。这样的定义可以正确反映买入股票时财务状况的变化,即减少了相应的金额。
🦆
题解中的状态转移方程`dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1])`中,`dp[i-1][1] + prices[i-1]`代表什么意义?
在这个状态转移方程中,`dp[i-1][1] + prices[i-1]`代表如果前一天(第 i-1 天)持有股票,并且选择在第 i 天卖出股票,所能获得的利润。这里 `dp[i-1][1]` 是第 i-1 天持有股票的最大利润,而 `prices[i-1]` 是第 i 天的股票价格。将这两者相加,就得到了在第 i 天卖出股票后的总利润。这种计算方式帮助确定是否卖出股票在第 i 天能获得更高的利润。
🦆
在动态规划数组初始化时,为什么`dp[0][1]`被初始化为负无穷?这样的初始化有什么特殊的意义?
在动态规划中,`dp[0][1]` 被初始化为负无穷是为了正确处理边界情况。`dp[0][1]` 表示在第 0 天结束时持有股票的最大利润,但实际上第 0 天开始时我们还没有进行任何交易,因此不可能持有股票。将其初始化为负无穷可以防止第一天买入股票的情况被错误地忽视或处理,因为任何正数(利润)与负无穷比较时,选取的将是正数,这反映了如果第一天买入股票的情况。这种初始化确保了动态规划的逻辑正确性和算法的有效性。

相关问题