leetcode买卖股票的最佳时机IIIIIIIV含手续费含冷冻期

1次阅读

共计 6568 个字符，预计需要花费 17 分钟才能阅读完成。

出场率很高的系列面试题，半年内，头条 18 次，阿里 4 次，小米 3 次（我买了会员所以可以看到出场率）。最近要面试的必看。

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

注意：本题题限制交易次数为 1 次。

第 i 天
- 如果第 i 天持有股票。有两种可能会在第 i 天持有股票。
  1. 今天购买股票
  2. 今天之前就已经购买股票
- 如果第 i 天不持有股票。有两种可能会在第 i 天不持有股票。
  1. 今天本身就不持有股票
  2. 今天卖出本身持有的股票
第一天，股价为7
- 由购买股票属于支出，所有如果在第一天购买股票，最大利润为0 - 7 = -7
- 第一天不持有股票，利润为0
第二天，股价为1
- 我们需要将利润最大化，所以购买的股价越低越好。第二天股价为 1 是优于第一天的 7 的，所以我们应该选择在第二天购买股票，此时最大利润为 0 - 1 = -1。（由于本题本身限制了交易次数，所以不存在被除数 不等于 0 的情况）
- 第二天不持有股票，有两种可能（第二天本身就不持有股票，状态沿用前一天的状态。或者，以️今天的股价卖出当前持有的股票。）。第一种可能，最大收益为0, 第二种可能，最大收益为1 - 7 = -6，小于0。所以我们在第二天的最大收益应该是0。
第三天，股价为5
- 第三天股价为 5 比前一天要高，所以我们依然选择在前一天购买股票，持有股票时第三天最大利润依然为-1
- 第三天不持有股票，有两种可能。第一种可能是沿用前一日的状态，收益依然为0。第二种可能，以今天的股价卖出当前持有股票，收益为5 - 1 = 4（当前的股价 – 前一日持有股票时的最优值或者说成本最低值），结果是4，优于第一种可能。所以在第三天不持有股票的最大收益为4。

向后依次类推，找出，不持有股票的最优结果数组中的, 最大值即可。????（因为不持有股票时，才没有负担啊～～）。


var maxProfit = function(prices) {if (prices.length === 0 || prices.length === 1) {return 0}
    // dp1 数组存储第 `i` 天，持有股票的最大利润
    const dp1 = []
    dp1[0] = -prices[0]
    // dp2 数组存储第 `i` 天，不持有股票的最大利润
    const dp2 = []
    dp2[0] = 0
    
    for (let i = 1; i < prices.length; i++) {dp1[i] = Math.max(dp1[i - 1], -prices[i])
        dp2[i] = Math.max(dp2[i - 1], prices[i] + dp1[i - 1])
    }
    
    return dp2[dp2.length - 1]
};

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

注意：本题不限制交易次数（309 题，714 题都可以看作是本题的引申）

与第一题不同，本题是可以进行无限次的交易。所以我们的收益是可以累加的。对状态转移方程式的影响，最直接的体现，就是对于 第i天持有股票的最优解 我们需要考虑前一天收益，而不是从 0 开始。所以，持有股票的状态转移方程式由，Max(前一天的状态, 0 - 今天的股价)变为Max(前一天的状态，前一天的最优收益 - 今天的股价）。

我们按照上题的推导逻辑，依次类推即可。最后，返回最后一天 不持有股票 时的最佳收益即可。


/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {if (prices.length === 0 || prices.length === 1) {return 0}
    
    const dp1 = []
    dp1[0] = -prices[0]
    
    const dp2 = []
    dp2[0] = 0
    
    for (let i = 1; i < prices.length; i++) {dp1[i] = Math.max(dp1[i - 1], dp2[i - 1] - prices[i])
        dp2[i] = Math.max(dp2[i - 1], prices[i] + dp1[i - 1])
    }
    
    return dp2[prices.length - 1]
};

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

示例 1:

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

本题是 122 题的变种，我们只需要在卖出股票时，考虑手续费 fee 即可。


/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {if (prices.length === 0 || prices.length === 1) {return 0}
    
    const dp1 = []
    dp1[0] = -prices[0]

    const dp2 = []
    dp2[0] = 0
    
    for (let i = 1; i < prices.length; i++) {dp1[i] = Math.max(dp1[i - 1], dp2[i - 1] - prices[i])
        dp2[i] = Math.max(dp2[i - 1], prices[i] + dp1[i - 1] - fee)
    }
    
    return dp2[dp2.length - 1]
};

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

本题依然是 122 题的变种，但是又有所区别。

交易股票分为买入，卖出两步。买入的操作是受到了冷冻期的限制，但是卖出是不受冷冻期的限制的。根据冷冻期的规则，我们需要将 持有股票的状态转移方程 调整为上图所示。但是很多人看到上面的公式，都会提出下面这个疑问。

????️Q：第 i 天持有股票的最优状态为什么要从第 i - 2 天不持有的状态获得，第 i-1 天就一定是冷冻期吗？

????A: 第 i 天持有股票的方式有两种可能。第一种可能，本身就持有股票，延续 i-1 天的状态 。第二种可能， 以第 i 天的股价购买股票 ，那么我们就需要考虑，第i-1 天不持有股票状态。

如果第 i-1 天是冷冻期。那么第 i-1 天的状态必然和第 i-2 天相等。

如果第 i-1 天不是是冷冻期。有两种可能。第一种可能，第 i-1 天本身就不持有股票，那么我们就需要得到第 i-2 天的状态 。第二种可能，第i-1 天卖出股票，由于冷冻期的限制，第 i 天就不能购买股票，所以这种可能不成立（无论是不是冷冻期，我们都不能在第 i-1 天卖出股票）。

通过上面的分析可知。无论第 i-1 天是不是冷冻期，我们都要从第 i-2 天不持有股票的最优解进行计算。


/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {if (prices.length === 0 || prices.length === 1) {return 0}
    
    const dp1 = []
    dp1[0] = -prices[0]

    const dp2 = []
    dp2[0] = 0
    
    for (let i = 1; i < prices.length; i++) {let temp = dp2[i - 2] === undefined ? 0 : dp2[i - 2]
        dp1[i] = Math.max(dp1[i - 1], temp - prices[i])
        dp2[i] = Math.max(dp2[i - 1], prices[i] + dp1[i - 1])
    }
    
    return dp2[dp2.length - 1]
};

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

本题的思考需要增加一个纬度，之前我们只需要考虑持有与不持有 两种情况，我们在两种情况上，增加到四种情况。持有股票，还有两次交易机会 ， 持有股票，还有一次交易机会 ， 不持有股票，还有两次交易机会 ， 不持有股票，还有一次交易机会。


/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {if (prices.length === 0 || prices.length === 1) {return 0}
    
    // 持有股票
    const dp1 = [[-prices[0]], // 还剩下两次交易机会
        [-prices[0]] // 还剩下一次交易机会
    ]
    // 不持有股票
    const dp2 = [[0], // 还剩下两次交易机会
        [0] // 还剩下一次交易机会
    ]
    
    for (let i = 1; i < prices.length; i++) {
        // 持有股票，还有两次交易机会
        dp1[0][i] = Math.max(dp1[0][i - 1], -prices[i])
        // 持有股票，还有一次交易机会
        dp1[1][i] = Math.max(dp1[1][i - 1], dp2[0][i - 1] - prices[i])
        // 不持有股票，还有两次交易机会
        dp2[0][i] = Math.max(dp2[0][i - 1], prices[i] + dp1[0][i - 1]) 
        // 不持有股票，还有一次交易机会
        dp2[1][i] = Math.max(dp2[1][i - 1], prices[i] + dp1[1][i - 1])
    }
    
    return dp2[1][prices.length - 1]
};

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2。

示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3。

本题是 123 题的衍生，在 leetcode 用例中，会有因为 k 过大，导致 dp 数组过大，导致内存溢出的问题。

长度为 n 的数组，最多进行 n/2 次的交易，所以所以 k 大于n/2，就相当于不限制交易次数, 我们就可以把本题当作第 122 题处理。


/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(k, prices) {if (prices.length === 0 || prices.length === 1) {return 0}
    
    if (k === 0) {return 0}
    
    if (k > prices.length / 2) {k = -1}
    
    const dp1 = []
    const dp2 = []
    
    if (k == -1) {dp1[0] = -prices[0]
        dp2[0] = 0
    } else {for (let i = 0; i < k; i++) {dp1.push([-prices[0]])
            dp2.push([0])
        }
    }
    
    for (let i = 1; i < prices.length; i++) {if (k === -1) {dp1[i] = Math.max(dp1[i - 1], dp2[i - 1] - prices[i])
            dp2[i] = Math.max(dp2[i - 1], prices[i] + dp1[i - 1])
        } else {for (let j = 0; j < k; j++) {if (j === 0) {dp1[j][i] = Math.max(dp1[j][i - 1], -prices[i]) 
                } else {dp1[j][i] = Math.max(dp1[j][i - 1], dp2[j - 1][i - 1] - prices[i])
                }
                dp2[j][i] = Math.max(dp2[j][i - 1], prices[i] + dp1[j][i - 1]) 
                dp2[j][i] = Math.max(dp2[j][i - 1], prices[i] + dp1[j][i - 1])
            }
        }
    }
    
    if (k === -1) {return dp2[prices.length - 1]
    } else {return dp2[k - 1][prices.length - 1]
    }
};

????️Q：今天的最优解，是基于前一天的最优解得到的，这样可以保证全局最优吗？

????A：我们可以把每一天当作最后一天。在最后一天，我们️收益值基于两种可能。第一种可能，最后一天时我们没有股票，
由于是最后一天所以，我们也不能买入股票，只能维持前一天的收益值。第二种可能，最后我们手上恰好还有股票，我们只能选择将它卖出，我们的收益值取决于 当天的股价 以及 买入的价格（持有股票的最优值），当天的股价是确定以及肯定的，如果 买入的价格 不是最优值，我们必然无法得到收益的最大值。

[Most consistent ways of dealing with the series of stock problems
](https://leetcode.com/problems…

正文完

leetcode

发表至： javascript

2019-10-21

0

关于javascript:笔记JS异步编程单线程定时器

关于javascript:Nodejs无处不在的环境变量

React Fiber 架构理解

使用Web-Animations-API创建炫酷动画

八皇后问题DFS深度优先搜索

leetcode买卖股票的最佳时机IIIIIIIV含手续费含冷冻期

前言

121. 买卖股票的最佳时机（简单）

原题

思路

代码

122. 买卖股票的最佳时机 II（简单）

原题

思路

代码

714. 买卖股票的最佳时机含手续费（中等）

原题

思路

代码

309. 最佳买卖股票时机含冷冻期（中等）

原题

思路

代码

123. 买卖股票的最佳时机 III（困难）

原题

思路

代码

188. 买卖股票的最佳时机 IV（困难）

原题

思路

代码

QA

参考

站内搜索