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

红太狼 2022-09-15 15:56 159阅读 0赞

## 前言 ##

题目：[714. 买卖股票的最佳时机含手续费][714.]

参考题解：[买卖股票的最佳时机含手续费-掘金-GeekQiaQia][-_-GeekQiaQia]

--------------------

## 提交代码 ##

我没想出来，如何使用贪心来解决这道题目。

下面代码和思路，来自参考题解。

将手续费买入时进行计算，即可得到一种贪心的方法；

我们定义`buy`表示，最大化利益的前提下，当我们手上有一只股票时，那么他的买入最低价格； 或者，表示，排除不值得更新之后，相对上升过程中，之前卖出股票的价格。

*  初始化为`buy=prices[0]+fee`;
 *  如果当前股票`prices[i]+fee<buy`;则我们更新最低买入价格buy;
 *  如果当前股票大于buy,则我们可以直接卖出获得利润
    
     *  `profit=prices[i]-buy`;
     *  但是此时我们卖出可能不是最优解，比如：第二天价格继续上升；
     *  将buy更新为prices\[i\]:`buy=prices[i]` ;
     *  如果第二天价格继续上升，我们将获得`prices[i+1]-prices[i]`,此时，加上前一天`prices[i]-buy`的收益，等于`prices[i+1]-buy`。相当于，连续(排除不值得更新之后)买入/卖出，只有第一笔需要手续费。
 *  其余情况，不值得更新/卖出；

class Solution {
    public:
        int maxProfit(vector<int>& prices, int fee) {
            int profit = 0;
            
            // 买入的时候，将手续费算上
            int buy = prices[0] + fee; // 题目保证1 <= prices.length <= 5 * 10^4
            for(int i=0; i<prices.size(); i++){
                if(prices[i]+fee < buy){
                    buy = prices[i] + fee; // 以最低的价格买入点
                }else if(prices[i] > buy){
                    profit += prices[i]-buy; // 累计收益
                    buy = prices[i];  // 如果是在峰顶卖出，下次直接进入if分支，更新buf
                                      // 如果不上升坡，非峰顶卖出，相当于本次没卖profit = (prices[i+1]-prices[i])+(prices[i]-buy) = prices[i+1]-buy
                                      // 连续卖出，相当于，只有第一笔需要手续费；这个代码技巧就很厉害了
                }
                
            }
    
            return profit;
        }
    };

[714.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
[-_-GeekQiaQia]: https://juejin.cn/post/7005945841051516936