如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习校招总结offer选择也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# 714. 买卖股票的最佳时机含手续费

力扣原题链接(点我直达) (opens new window)

给定一个整数数组 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.
1
2
3
4
5
6
7
8

注意:

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

# 第一版,动态规划,优化

执行用时 :128 ms, 在所有 cpp 提交中击败了80.36%的用户

内存消耗 :19.7 MB, 在所有 cpp 提交中击败了24.70%的用户

当天买入的最大收益是:1、昨天买入的最大收益,即当天不买入。2、昨天卖出的最大收益-当天股票价格-手续费。

当天卖出的最大收益是:1、昨天卖出的最大收益,即当天无法卖出。2、昨天买入的最大收益+当天股票价格。

手续费算在买入和卖出里都是一样的结果。
思路:动态规划

代码


class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
      if (prices.empty()) return 0;

	int size = prices.size();
	vector<int> hold(size), sold(hold);
	hold[0] = -prices[0];
	for (int i = 1; i < size; ++i) {
		//表示没有股票在手时,身上含有的金额,状态的变化。
		sold[i] = max(sold[i - 1], hold[i - 1] + prices[i] - fee);
		//表示有股票在手时,含有的金额状态的变化
		hold[i] = max(hold[i - 1], sold[i - 1] - prices[i]);
	}
	return sold[size - 1];
};
优化空间
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if (prices.empty()) return 0;
        int size = prices.size();
        int sold = 0, hold = -prices[0];        
        for (int i = 1; i < size; ++i) {
            sold = max(sold, hold + prices[i] - fee);
            hold = max(hold, sold - prices[i]);
        }
        return sold;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 第二版,贪心算法

public int maxProfit(int[] prices, int fee) {
		 int len = prices.length;
		 if(len == 0 || len == 1) return 0;//边界条件
		 int sum = 0,cur=0;
		 int max = prices[0],min = prices[0];
		 for(int i=1;i<len;i++) {
			 min = Math.min(min, prices[i]);//记录当前最小值
			 max = Math.max(max, prices[i]);//记录当前的最大值
			 cur = Math.max(cur, prices[i]-min-fee);//记录当前可能的最大收益
			 if(max - prices[i] > fee) {//如果掉价超过了手续费还不如花手续费买卖股票
				 sum += cur;//赶紧抛出手中股票,能转多少是多少,然后又重新开始
				 min = prices[i];
				 max = prices[i];
				 cur = 0;
			 }
		 }
		 sum += cur;
		 return sum;
	 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19