手续费"/>
力扣:714. 买卖股票的最佳时机含手续费
力扣:714. 买卖股票的最佳时机含手续费
题目:
给定一个整数数组 prices,其中 prices[i]表示第 i 天的股票价格 ;整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。
注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。
思路:
一:在遍历整个数组过程中我们包含如下操作:
开始一笔交易:
选定buy
有更小的buy,buy修改
有更大的sell,sell修改即合并区间
是否开始下一笔交易:
即不会产生合并区间的情况。通过方法①来实现
二:假设prices为:【1,4,3,8,4,9】
选择:【1,8】【4,9】
三:过程模拟
脑海中画出x,y坐标系,此时横坐标为值下标,纵坐标为值。
此时看题目可知,1,4可选,2,8可选。但是其选择了1,8。原因是什么呢?我们假设这个过程是怎样的来一步步反向推导出每一个问题的解决方案。因为一笔交易有手续费我们可以把手续费放到买入的钱里面去。我们遍历整个过程,遍历到1,我们选择买入,此时买入的是3,遍历到4按常理来说此时的4大于3所以我们选择卖出。遍历到8——此时我们进行反向推导。答案是【1,8】那么我们对3是不进行操作的,但是按常理来说我们应该入3,然后8的时候卖出啊。此时假如我们3买入,那么肯定有一个地方是卖出的我们设这个位置的值为x。此时我们分别计算一下3不买入和3买入所获得的利益。
①:
- 3买入:x-5+4-3 = x-4
- 3不买入:x-3
很明显3不买入比3买入利益更大,所以遍历到3的时候我们可以选择不买入。所以当我们遍历到一个值且已经有一个卖出的值后,我们可以通过①判断方法来看是否应该在这天买入。
同时当我们遍历到一个值且已经有一个卖出的值后,我们可以判断此值是否比卖出的那天价格更高,若更高则。prices+当前天的值-卖出那天的值即实现反悔的操作。如此便实现了整个过程。通过这两种方式的判断即可实现是合并操作,和重新产生一笔交易操作。
代码实现:
class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int result = 0;int minPrice = prices[0]; // 记录最低价格for (int i = 1; i < prices.size(); i++) {// 情况二:相当于买入if (prices[i] < minPrice) minPrice = prices[i];// 情况三:保持原有状态(因为此时买则不便宜,卖则亏本)if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {continue;}// 计算利润,可能有多次计算利润,最后一次计算利润才是真正意义的卖出if (prices[i] > minPrice + fee) {result += prices[i] - minPrice - fee;minPrice = prices[i] - fee; // 情况一,这一步很关键}}return result;}
};
更多推荐
力扣:714. 买卖股票的最佳时机含手续费
发布评论