[Leetcode 每日精选](本周主题-股票) 714. 买卖股票的最佳时机含手续费
发布日期:2021-06-29 07:11:36
浏览次数:4
分类:技术文章
本文共 3108 字,大约阅读时间需要 10 分钟。
题目难度: 中等
今天我们继续来做股票包含"手续费"的这道中等问题, 这道题和昨天"冷冻期"的问题挺类似的. 大家在我的公众号"每日精选算法题"中的聊天框中回复 股票 就能看到了当前已经更新的股票系列了
大家有什么想法建议和反馈的话欢迎随时交流, 包括但不限于公众号聊天框/知乎私信评论等等~
题目描述
给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。
- 0 < prices.length <= 50000.
- 0 < prices[i] < 50000.
- 0 <= fee < 50000.
题目样例
示例
输入
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.
题目思考
- 把冷冻期换成手续费后, 我们还能利用类似的动态规划思路吗?
解决方案
思路
- 分析
- 这道题我们同样可以采用动态规划的思路, 因为当前最大收益和之前的最大收益有很强的关联关系. P.S. 想要回顾昨天冷冻期思路的同学们可以在公众号"每日精选算法题"里回复 股票 查看 (309. 最佳买卖股票时机含冷冻期)
- 推导
- 设 dp[i]表示在第 i 天卖出时能获得的最大收益, 相比冷冻期, 这次我们可以直接利用 i-1 天的结果了
- 我们仍然需要维护 mnprice, 表示当前 i 天之前的最低价格. 这个最低价格仍然是[j:i-1]之间的最低价格, j 是上次卖出的日期
- 同样的, mxdp 表示在 i-1 天及之前的最大 dp 值. 如果当前的 dp[i-1] 比之前的 mxdp 大的话, 我们就更新 mxdp 和 mnprice (此时新的 mnprice 只能为 prices[i-1] 了)
- 同样的, 第 i 天卖出的最大收益为
dp[i] = max(mxdp + prices[i] - mnprice - fee)
, 多了一个减去 fee 的部分. 由于 prices[i]和 fee 是固定的, 所以我们只需要求max(mxdp - mnprice)
. 可以将它们视为一个整体, 再引入一个变量 mxdiff 来求截止到 i 天的最大mxdp - mnprice
即可. (因为不一定 i-1 天卖出就是之前所能得到的最大收益, 有可能更早卖出才是)
- 总结
- 万变不离其宗, 核心转移方程仍为
dp[i] = max(mxdp + prices[i] - mnprice - fee) = prices[i] - fee + mxdiff
, 只是多了一个手续费的固定数值 - 下面的代码中对每一步有详细的注释, 帮助大家理解~
- 万变不离其宗, 核心转移方程仍为
复杂度
- 时间复杂度 O(N): 需要遍历整个数组一遍
- 空间复杂度 O(1): 这里对 dp 数组进行了空间优化, 只需要存前一个 dp 值和当前 dp 值即可, 所以是 O(1)
代码
Python 3
class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: # 只需要使用两个变量存dp # 仍然需要mxdp, mnprice和mxdiff n = len(prices) # predp - 第i-1天卖出的最高收益 # curdp - 第i天卖出的最高收益 # mxdp - i-1天及之前所能获得的最高收益 predp, curdp, mxdp = 0, 0, 0 # mnprice - 上一次卖出之后到当前的最低价格 # mxdiff - 最大的mxdp-mnprice mnprice, mxdiff, res = float('inf'), -float('inf'), 0 for i in range(1, n): # 更新最低价格 mnprice = min(mnprice, prices[i - 1]) if predp > mxdp: # 当前predp比mxdp更大, 更新它 mxdp = predp # 同时mnprice也要被更新, 因为上一次卖出是i-1, 现在可能值只能是prices[i-1]了(即立即买入) mnprice = prices[i - 1] # 更新mxdp - mnprice这个整体的最大值 mxdiff = max(mxdiff, mxdp - mnprice) # 更新predp和curdp, curdp就是prices[i] + mxdiff - fee predp = curdp curdp = prices[i] + mxdiff - fee # 更新最终结果 res = max(res, curdp) return res
C++
class Solution { public: int maxProfit(vector & prices, int fee) { int predp = 0, curdp = 0, mxdp = 0; int mnprice = INT_MAX, mxdiff = INT_MIN, res = 0; for (int i = 1; i < prices.size(); ++i) { mnprice = min(mnprice, prices[i - 1]); if (predp > mxdp) { mxdp = predp; mnprice = prices[i - 1]; } mxdiff = max(mxdiff, mxdp - mnprice); predp = curdp; curdp = prices[i] + mxdiff - fee; res = max(res, curdp); } return res; }};
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
转载地址:https://blog.csdn.net/zjulyx1993/article/details/106554539 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月13日 12时36分29秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
声网Agora 2020 年 Q3 财报
2019-04-29
声网 X 牛客网 200万场视频面试背后的实时互动技术支撑
2019-04-29
声网X智能作业灯 台灯如何成为在线作业辅导新神器?
2019-04-29
RTC 月度小报 11 月 | 开发者社区全新上线、WebRTC 镜像、大会回顾……
2019-04-29
社区「学习周」喊你来打卡
2019-04-29
RTE 大会回顾 | 基于 Web 引擎技术的 Web 内容录制
2019-04-29
CODING DevOps 演讲回顾:声网 Agora SDK 测试最佳实践
2019-04-29
声网合伙人王骅:聊聊企业拥抱全球化 关键是什么?
2019-04-29
冲顶大会、HQ火了,该如何打造一款在线答题App呢?
2019-04-29
教你如何结合WebRTC与TensorFlow实现图像检测
2019-04-29
直播问答瓶颈及技术方案解读
2019-04-29
技术架构解读:直播答题如何组队开黑
2019-04-29
深入浅出,ARCore开发原理
2019-04-29
H5直播答题并不难,看完这篇你也会
2019-04-29
18个实时音视频开发中会用到开源项目
2019-04-29
吃鸡游戏百人语音,如何实现“听声辩位”找队友
2019-04-29
如何基于Agora Web SDK实现小程序互动连麦
2019-04-29
如何结合 CallKit 和 Agora SDK 实现视频 VoIP 通话应用
2019-04-29
ARCore 1.0 实践:在直播场景中加入AR特效
2019-04-29