第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0309. 最佳买卖股票时机含冷冻期

题目地址(309. 最佳买卖股票时机含冷冻期)

题目描述

1
给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​
2
3
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
4
5
你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
6
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
7
示例:
8
9
输入: [1,2,3,0,2]
10
输出: 3
11
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
Copied!

前置知识

公司

  • 阿里
  • 腾讯
  • 字节

记忆化递归

思路

用 f(i, state) 表示第 i 天(从 0 开始),当前状态是 state 的最大利润。
  • state 为 0 表示手上没有股票
  • state 为 1 表示手上有股票
  • state 为 -1 表示手上没有股票,但是在冷冻期,所以不能买。
那么转移方程就容易了。
  • 如果 state 为 0,那么当前可以什么都不做,也可以买入,也就是说不能卖出了。因此最大利润就是两种的最大值。
1
max(f(i+1, 0), f(i+1, 1) - prices[i])
Copied!
  • 如果 state 为 1,那么当前可以什么都不做,也可以卖出,也就是说不能买入了。因此最大利润就是两种的最大值。
1
max(f(i+1, 1), f(i+1, -1) + prices[i])
Copied!
  • 如果 state 为 -1,那么当前只能什么都不做,因此最大利润维持不变,但是状态变为 0。(因为冷冻期只有一天,思考下如果冷冻期是 k 天如何修改我们的逻辑?)
1
f(i+1, 0)
Copied!
临界条件就是 i == n - 1,此时如果 state == 1, 我们可以将其卖掉,否则无法卖出。

代码

代码支持:Python3
Python3 Code:
1
class Solution:
2
def maxProfit(self, prices):
3
if not prices:
4
return 0
5
n = len(prices)
6
7
@lru_cache(None)
8
def f(i, state):
9
if i == n - 1:
10
return prices[i] if state == 1 else 0
11
12
if state == -1:
13
return f(i + 1, 0)
14
if state == 0:
15
return max(f(i + 1, 0), -prices[i] + f(i + 1, 1))
16
if state == 1:
17
return max(prices[i] + f(i + 1, -1), f(i + 1, 1))
18
19
return f(0, 0)
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度: 状态总数为 3 * n ,单个状态所需时间为 $O(1)$,因此时间复杂度为 $O(n)$
  • 空间复杂度:状态总数为 3 * n ,因此空间复杂度为 $O(n)$

动态规划

思路

这是一道典型的 DP 问题, DP 问题的核心是找到状态和状态转移方程。
这道题目的状态似乎比我们常见的那种 DP 问题要多,这里的状态有 buy sell cooldown 三种,我们可以用三个数组来表示这这三个状态,buy,sell, cooldown。其中:
  • buy[i]表示第 i 天,且手里有股票(不在冷冻期)的最大利润
  • sell[i]表示第 i 天,且手里没有股票的最大利润
  • cooldown[i]表示第 i 天,且手里有股票(但是在冷冻期不能卖)的最大利润
我们思考一下,其实 cooldown 这个状态数组似乎没有什么用,因为 cooldown 不会对profit产生任何影响。 我们可以进一步缩小为两种状态。
  • buy[i] 表示第 i 天,且手里有股票的最大利润
  • sell[i] 表示第 i 天,且手里没股票的最大利润
对应的状态转移方程如下:
这个需要花点时间来理解
1
buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
2
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
Copied!
我们来分析一下,buy[i]对应第 i 的 action 只能是 buy 或者 cooldown。(如果是 sell 的话手里就没有股票了)
  • 如果是 cooldown,那么 profit 就是 buy[i - 1]
  • 如果是 buy,那么就是前一个卖的profit减去今天买股票花的钱,即 sell[i -2] - prices[i]
注意这里是 i - 2,不是 i-1 ,因为有 cooldown 一天的限制
sell[i]对应第 i 的 action 只能是 sell 或者 cooldown。
  • 如果是 cooldown,实际上就是 sell[i - 1]。
  • 如果是 sell,那么利润就是前一次买的时候获取的利润加上这次卖的钱,即 buy[i - 1] + prices[i]

关键点解析

  • 多状态动态规划

代码

代码支持:JS
JS Code:
1
/*
2
* @lc app=leetcode id=309 lang=javascript
3
*
4
* [309] Best Time to Buy and Sell Stock with Cooldown
5
*
6
*/
7
/**
8
* @param {number[]} prices
9
* @return {number}
10
*/
11
var maxProfit = function (prices) {
12
if (prices == null || prices.length <= 1) return 0;
13
14
// 定义状态变量
15
const buy = [];
16
const sell = [];
17
// 寻常
18
buy[0] = -prices[0];
19
buy[1] = Math.max(-prices[0], -prices[1]);
20
sell[0] = 0;
21
sell[1] = Math.max(0, prices[1] - prices[0]);
22
for (let i = 2; i < prices.length; i++) {
23
// 状态转移方程
24
// 第i天只能是买或者cooldown
25
// 如果买利润就是sell[i - 2] - prices[i], 注意这里是i - 2,不是 i-1 ,因为有cooldown的限制
26
// cooldown就是buy[i -1]
27
buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
28
// 第i天只能是卖或者cooldown
29
// 如果卖利润就是buy[i -1] + prices[i]
30
// cooldown就是sell[i -1]
31
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
32
}
33
34
return Math.max(buy[prices.length - 1], sell[prices.length - 1], 0);
35
};
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$(同上)
  • 空间复杂度:$O(n)$(同上)

相关题目

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了, 大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。我是 lucifer,维护西湖区最好的算法题解,Github 超 40K star 。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 另外我整理的 1000 多页的电子书已限时免费下载,大家可以去我的公众号《力扣加加》后台回复电子书获取。