LeetCode 121. 买卖股票的最佳时机 DP题解，熟悉简单DP问题。

题目

121. 买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

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

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

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

DP

思路

李煜东著《算法竞赛进阶指南》，摘录如下：：

动态规划三要素：

  1. 状态；
  2. 阶段；
  3. 决策；

动态规划求解的三个基本条件：

  1. 子问题重叠性；
  2. 无后效性；
  3. 最优子结构性质；

DP解题关键要素：

要素
状态表示 dp[i]表示当前能买入的最低价格、prices[i]表示当前天卖出的价格；
阶段划分 子序列结尾；
转移方程 dp[i] = Min(prices(0,i))
边界 dp[0] = prices[0]
目标 Max(prices[i]-dp[i]) (0<=i<n)

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public int maxProfit(int[] prices) {
      int n = prices.length;
      // dp数组存储当前时刻前买入的最低价格
      int[] dp = new int[n];
      dp[0] = prices[0];
      int ans = 0;

      for (int i = 1; i < prices.length; i++) {
            dp[i] = Math.min(dp[i - 1], prices[i]);

            // 判断当前时刻卖出是否划算？
            if (prices[i] - dp[i] > ans) {
                  ans = prices[i] - dp[i];
            }
      }
      return ans;
}

观察发现，上述dp[]其实无需保留每一项的最小值，我们仅需记录窗口内的最小值即可，可通过滚动数组来优化空间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
* 使用滚动数组优化：只需维护窗口内的最低买入价格即可
*/
static class ScrollArray {
      /*
      * 执行用时：
      * 2 ms
      * , 在所有 Java 提交中击败了
      * 58.30%
      * 的用户
      * 内存消耗：
      * 58.2 MB
      * , 在所有 Java 提交中击败了
      * 5.05%
      * 的用户
      * 通过测试用例：
      * 211 / 211
      */

      public int maxProfit(int[] prices) {
      int minBuyPrice = prices[0];
      int ans = 0;

      for (int i = 1; i < prices.length; i++) {
            minBuyPrice = Math.min(minBuyPrice, prices[i]);
            ans = Math.max(prices[i] - minBuyPrice, ans);
      }
      return ans;
      }
}

复杂度分析

时间

整个过程仅需遍历一次入参数组，时间复杂度O(n)。

空间

写法1我们定义了prices大小的dp数组，空间复杂度O(n)。

写法2优化了空间占用，空间复杂度O(1)。