代码随想录贪心算法——买卖股票的最佳时机含手续费

题目

给定一个整数数组 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.

注意:

0 < prices.length <= 50000. 0 < prices[i] < 50000. 0 <= fee < 50000

思路

本题相对于买卖股票的最佳时机||多添加了一个手续费的条件

买卖股票的最佳时机||中使用贪心不需要关心具体什么时候卖，只需要收集每天的正利润，最后得到的就是最大利润了

在本题中，因为有手续费的存在，所以需要考虑什么时候买卖了，因为计算所获得的利润，需要考虑利润可能不足以支付手续费的问题

使用贪心策略的话，就是最低值买，最高值（如果算上手续费还盈利）就卖

买入日期:遇到更低点就记录一下
卖出日期:只要当前价格大于（最低价格+手续费），就可以获得利润，具体哪一天的话，就是连续收获利润区间里的最后一天

收获利润操作的时候分成三种情况：

• 收获利润的这里天并不是收获利润区间的最后一天，继续收获利润
• 前一天是收获利润区间的最后一天（今天开始重新记录最小价格）
• 不作操作，保持原有状态

PS:本题贪心的思路比较难，DP才是常规做法，这里主要是拓展一下贪心的思路

java代码如下：

class Solution {
	public int maxProfit(int[] prices, int fee){
		int buy = fee + prices[0];//记录最小价格(包含手续费)
		int sum = 0;
		for(int p : prices){
			 if(p + fee < buy){//找最小价格(包含手续费)
				buy = p + fee;//更新最小价格(含手续费)
			}else if (p > buy){//如果当前价格大于最小价格(含手续费)
				sum += p - buy;//累计利润
				buy = p;//更新当前最小价格
			}
		}
		return sum;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15