PiggyBlog
Published on

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

Authors

声明：该文通过我个人写Prompt喂给AI产出

问题描述回顾

给定一个数组 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. 记录当前遇到的最小价格：在遍历过程中，我们始终记录到目前为止遇到的最小价格，这个价格是潜在的买入点。
  2. 计算当前价格与最小价格的差值：对于每一天的价格，我们计算如果在这一天卖出，能够获得的利润（即当前价格减去之前的最小价格）。
  3. 更新最大利润：在遍历过程中，我们不断更新能够获得的最大利润。

为什么这种方法有效？

  • 我们需要找到 prices[j] - prices[i] 的最大值，其中 j > i。
  • 如果我们固定 prices[j]，那么为了使 prices[j] - prices[i] 最大，prices[i] 应该是 prices[0..j-1] 中的最小值。
  • 因此，在遍历数组时，对于每一天的价格 prices[j]，我们只需要知道之前的最小价格，就可以计算当前的最大利润。
  • 因为我们每天都计算当前的最大利润，并加以维护，所以最后获得maxProfit就是最大利润。

关键点

  1. 初始化：
    • minPrice 初始化为第一天的价格或一个很大的值（如 Integer.MAX_VALUE）。
    • maxProfit 初始化为 0。
  2. 遍历过程：
    • 更新 minPrice：如果当前价格比 minPrice 小，则更新 minPrice。
    • 计算当前利润：currentProfit = prices[i] - minPrice。
    • 更新 maxProfit：如果 currentProfit 大于 maxProfit，则更新 maxProfit。
  3. 结果：
    • 遍历结束后，maxProfit 就是能够获得的最大利润。

Java 实现

class Solution {
     public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int maxProfit = 0;
        int minPrice = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
        return maxProfit;
    }
}

代码解释

  1. 初始化：
    • minPrice 初始化为 Integer.MAX_VALUE，这样任何价格都会比它小，从而在第一次比较时被更新。
    • maxProfit 初始化为 0，表示初始时没有利润。
  2. 遍历数组：
    • 对于每一天的价格 price：
      • 如果 price 比 minPrice 小，说明找到了更低的买入点，更新 minPrice。
      • 计算 price - minPrice（即当前利润），如果比 maxProfit 大，则更新 maxProfit。
  3. 返回结果：
    • 遍历结束后，maxProfit 就是能够获得的最大利润。

复杂度分析

  • 时间复杂度：O(n)，因为我们只遍历数组一次。
  • 空间复杂度：O(1)，只使用了常数空间。

示例演示

以 prices = [7,1,5,3,6,4] 为例：

  • 初始：minPrice = MAX_VALUE, maxProfit = 0
  • i=0: price=7
    • minPrice = 7, maxProfit = 0
  • i=1: price=1
    • minPrice = 1, maxProfit = 0
  • i=2: price=5
    • 5 - 1 = 4 > 0 => maxProfit = 4
  • i=3: price=3
    • 3 - 1 = 2 < 4 => maxProfit 不变
  • i=4: price=6
    • 6 - 1 = 5 > 4 => maxProfit = 5
  • i=5: price=4
    • 4 - 1 = 3 < 5 => maxProfit 不变
  • 最终结果：5

边界情况

  1. 空数组或单元素数组：
    • 直接返回 0，因为没有交易机会。
  2. 价格一直下跌：
    • maxProfit 始终为 0。
  3. 价格一直上涨：
    • minPrice 始终是第一个价格，maxProfit 是最后一个价格减去第一个价格。

总结

这个问题通过一次遍历和贪心的思想（始终记录当前最小价格和最大利润）高效地解决了问题。关键在于理解如何通过维护最小价格来简化计算最大利润的过程。

动态规划解法思路

虽然这道题可以用贪心算法高效解决，但也可以用动态规划（DP）的思想来解决。动态规划的思路是定义状态并找到状态转移方程。

状态定义

我们可以定义以下状态：

  • dp[i][0]：表示第 i 天结束时不持有股票时的最大利润。
  • dp[i][1]：表示第 i 天结束时持有股票时的最大利润。

初始状态

  • dp[0][0] = 0：第 0 天不持有股票，利润为 0。
  • dp[0][1] = -prices[0]：第 0 天持有股票，说明在第 0 天买入，利润为 -prices[0]（因为花钱买入，所以是负的）。

状态转移方程

  1. dp[i][0]（第 i 天不持有股票）：
    • 可能是前一天就不持有股票：dp[i-1][0]。
    • 也可能是前一天持有股票，今天卖出：dp[i-1][1] + prices[i]。
    • 取两者的最大值：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])。
  2. dp[i][1]（第 i 天持有股票）：
    • 可能是前一天就持有股票：dp[i-1][1]。
    • 也可能是今天才买入股票（因为只能交易一次，所以之前不能有交易）：-prices[i]。
    • 取两者的最大值：dp[i][1] = max(dp[i-1][1], -prices[i])。

最终结果

最后一天不持有股票时的利润就是最大利润，即 dp[n-1][0]（因为卖出股票后才能获得利润）。

Java 实现

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        int[][] dp = new int[n][2];

        // 初始状态
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < n; i++) {
            // 第 i 天不持有股票：前一天就不持有 或 前一天持有今天卖出
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            // 第 i 天持有股票：前一天就持有 或 今天买入（因为只能交易一次，所以之前不能有交易）
            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
        }

        return dp[n-1][0]; // 最后一天不持有股票时的利润
    }
}

空间优化

由于 dp[i] 只依赖于 dp[i-1]，我们可以用两个变量代替二维数组，优化空间复杂度到 O(1)：

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int dp0 = 0;           // 不持有股票时的利润
        int dp1 = -prices[0];  // 持有股票时的利润

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

        return dp0;
    }
}

动态规划与贪心的对比

  • 贪心算法：
    • 时间复杂度：O(n)，空间复杂度：O(1)。
    • 核心思想：遍历时记录最小价格，并计算当前价格与最小价格的差值。
  • 动态规划：
    • 时间复杂度：O(n)，空间复杂度：O(1)（优化后）。
    • 核心思想：定义状态并推导状态转移方程，更通用（适用于更复杂的股票买卖问题）。

为什么动态规划也能解决这个问题？

虽然贪心算法更高效，但动态规划的思路更通用，可以扩展到更复杂的股票买卖问题（如多次交易、含手续费等）。本题的动态规划解法可以看作是贪心算法的另一种形式，因为 dp0 和 dp1 的更新逻辑与贪心算法中的 minPrice 和 maxProfit 类似。

示例演示

以 prices = [7,1,5,3,6,4] 为例：

  • 初始：
    • dp0 = 0, dp1 = -7
  • i=1: price=1
    • dp0 = max(0, -7 + 1) = max(0, -6) = 0
    • dp1 = max(-7, -1) = -1
  • i=2: price=5
    • dp0 = max(0, -1 + 5) = max(0, 4) = 4
    • dp1 = max(-1, -5) = -1
  • i=3: price=3
    • dp0 = max(4, -1 + 3) = max(4, 2) = 4
    • dp1 = max(-1, -3) = -1
  • i=4: price=6
    • dp0 = max(4, -1 + 6) = max(4, 5) = 5
    • dp1 = max(-1, -6) = -1
  • i=5: price=4
    • dp0 = max(5, -1 + 4) = max(5, 3) = 5
    • dp1 = max(-1, -4) = -1
  • 最终结果：dp0 = 5

总结

  • 贪心算法：简单高效，适用于本题。
  • 动态规划：通用性强，适用于更复杂的股票买卖问题。
  • 两种方法的时间复杂度都是 O(n)，空间复杂度都是 O(1)（优化后）。
View on GitHub