Skip to content

Latest commit

 

History

History
247 lines (191 loc) · 8.68 KB

买卖股票的最佳时机.md

File metadata and controls

247 lines (191 loc) · 8.68 KB
Raw

买卖股票的最佳时机

maxProfit

思路

我开始还以为和数组那个买股票最佳时期题目一样。注意区别，只允许交易一次￣□￣｜｜

1. 暴力枚举

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  var maxprofit = 0
  for(var i=0;i<prices.length;i++){
   for(var j=i+1;j<prices.length;j++){
        var profit = prices[j] - prices[i];
        if (profit > maxprofit) maxprofit = profit;
   }   
  }
  return maxprofit
};

2. 暴力枚举的优化

我们发现：其实只需要关心之前（不包括现在）看到的最低股价，于是在遍历的过程中，记录下之前看到的最低股价，就可以省去内层循环。

var  maxProfit = function(prices) {
        var len = prices.length;
        if (len < 2) {
            return 0;
        }
        var res = 0;
        // 表示在当前位置之前的最小值，假设修正法（打擂台法）
        var minVal = prices[0];
        // 注意：这里从 1 开始
        for (var i = 1; i < len; i++) {
            res = Math.max(res, prices[i] - minVal);
            minVal = Math.min(minVal, prices[i]);
        }
        return res;
    }

3. 动态规划

动态规划的 5 个步骤：

  1. 设定状态

这道题其实是一个典型的二维 dp 问题。“动态规划”用于多阶段最优化问题的求解。这里天数代表每个阶段，即一天一天看，设置为第一维。为了消除后效性（前面的状态确定下来以后不会因为后面状态而更改），将当天是否持股设置为第二维的状态。于是：

状态 dp[i][j] 表示：在索引为 i 的这一天，用户手上持股状态为 j 所获得的最大利润。

说明：

j 只有 2 个值：0 表示不持股（特指卖出股票以后的不持股状态），1 表示持股。 “用户手上不持股”不代表用户一定在索引为 i 的这一天把股票抛售了； 2. 思考状态转移方程

dp[i][0] 怎样转移？

  • dp[i - 1][0] ：当然可以从昨天不持股转移过来，表示从昨天到今天什么都不操作，这一点是显然的；

  • dp[i - 1][1] + prices[i]：昨天持股，就在索引为 i 的这一天，我卖出了股票，状态由 1 变成了 0，此时卖出股票，因此加上这一天的股价。

综上：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

dp[i][1] 怎样转移？

  • dp[i - 1][1] ：昨天持股，今天什么都不操作，当然可以从昨天持股转移过来，这一点是显然的；

  • -prices[i]：注意：状态 1不能由状态 0 来，因为事实上，状态 0 特指：“卖出股票以后不持有股票的状态”，请注意这个状态和“没有进行过任何一次交易的不持有股票的状态”的区别。

因此，-prices[i] 就表示，在索引为 i 的这一天，执行买入操作得到的收益。注意：因为题目只允许一次交易，因此不能加上 dp[i - 1][0]。

综上：dp[i][1] = max(dp[i - 1][1], -prices[i]);

  1. 考虑初始值 第 0 天不持股，显然 dp[0][0] = 0；

第 0 天持股，显然dp[0][1] = -prices[0]。

  1. 考虑输出 从状态转移方程可以看出，每一天的状态都考虑了之前的状态。在只发生一次交易的情况下，持有这支股票一定不能使我们获得最大利润。因此输出是 dp[len - 1][0]，不可能是持股的状态 dp[len - 1][1]，

参考代码 3：

var maxProfit = function(prices) {
        var len = prices.length;
        if (len < 2) {
            return 0;
        }

        // 0：用户手上不持股所能获得的最大利润，特指卖出股票以后的不持股，非指没有进行过任何交易的不持股
        // 1：用户手上持股所能获得的最大利润

        // 注意：因为题目限制只能交易一次，因此状态只可能从 1 到 0，不可能从 0 到 1
        // int[][] dp = new int[len][2];
        var dp = [];
        for (var i = 0; i < len; i++) {
          var arr = []
          for (var j = 0; j < 2; j++) {
            arr.push("")
          }
          dp.push(arr)
        }
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (var i = 1; i < len; 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[len - 1][0];
    }

复杂度分析：

  • 时间复杂度：O(N)；
  • 空间复杂度：O(N)。

说明：如果我们一定要区分“不持有股票”的状态是“一开始不持有”和“卖出股票以后的不持有”，设置 3 个状态即可，我个人认为更加清晰。

下面状态的设置和状态转移方程均写在代码注释中：

参考代码 4：

var maxProfit = function(int[] prices) {
        var len = prices.length;
        if (len < 2) {
            return 0;
        }

        // 0：不进行任何操作
        // 1：用户执行了一次买入操作
        // 2：用户执行了一次卖出操作

        // 状态转移方程：
        // dp[i][0] 永远等于 0
        // dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        // dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])


        // 注意：如果是 `[7, 6, 5, 4, 3]` 这种波动，应该不交易，
        // 因此输出是：max(dp[len - 1][0], dp[len - 1][2])

        // int[][] dp = new int[len][3];
        var dp = [];
        for (var i = 0; i < len; i++) {
          var arr = []
          for (var j = 0; j < 3; j++) {
            arr.push("")
          }
          dp.push(arr)
        }

        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        // 这里状态 2 不应该有值，设置为 0 不影响正确性
        dp[0][2] = 0;
        for (var i = 1; i < len; i++) {
            // 可以不显式赋值，因为 int 的初值就是 0
            dp[i][0] = 0;
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
        }
        return Math.max(dp[len - 1][0], dp[len - 1][2]);
    }

复杂度分析：

  • 时间复杂度：O(N)；
  • 空间复杂度：O(N)。 说明：事实上，这一版代码，由于 dp[i][0] = 0 恒成立，和“参考代码 3”其实是等价的。
  1. 考虑是否可以状态压缩

由于 dp[i] 仅仅依赖于 dp[i - 1] ，因此，我们可以使用滚动数组的技巧压缩变量。下面根据“参考代码 3”进行修改：

参考代码 5：

    var maxProfit = function(prices) {
        var len = prices.length;
        if (len < 2) {
            return 0;
        }

        // int[][] dp = new int[2][2];
        var dp = [];
        for (var i = 0; i < 2; i++) {
          var arr = []
          for (var j = 0; j < 2; j++) {
            arr.push("")
          }
          dp.push(arr)
        }
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (var i = 1; i < len; i++) {
            dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i]);
            dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], -prices[i]);
        }
        return dp[(len - 1) & 1][0];
    }

复杂度分析：

  • 时间复杂度：O(N)；
  • 空间复杂度：O(1)，状态压缩以后相当于只用了 4 个变量。 我们继续观察“参考代码 3”，因为状态只能从 1 到 0，即先有状态 1 再有状态 0，我们在填写“状态表 dp” 的时候，只需要用 1 维，因此填表的时候，先写 0 再写 1 即可。

参考代码 6：（根据“参考代码 3”进行修改）

    var maxProfit = function(prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        var dp = [];
        dp[0] = 0;
        dp[1] = -prices[0];
        for (var i = 1; i < len; i++) {
            dp[0] = Math.max(dp[0], dp[1] + prices[i]);
            dp[1] = Math.max(dp[1], -prices[i]);
        }
        return dp[0];
    }

复杂度分析：

  • 时间复杂度：O(N)；
  • 空间复杂度：O(1)，状态压缩以后相当于只用了 2 个变量。 很有意思的是，可以将此时的数组 dp 语义化，dp[1] = Math.max(dp[1], -prices[i]); 等价于 dp[1] = Math.min(dp[1], prices[i]); 其实就是“参考代码 2” 中的 minVal，dp[0] 等价于 “参考代码 2” 中的 res。

参考原文：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/bao-li-mei-ju-dong-tai-gui-hua-chai-fen-si-xiang-b