力扣-单调递增的数字 & 买卖股票的最佳时机含手续费

738. 单调递增的数字

class Solution {
public:
    //题目中说到x<=y即可，也就是说299999也是单调递增的
    //贪心，局部最优推出全局最优，两个数字，当左边的比右边的大时，左边就可-1右边改为9
    //问题在于具体哪一位要-1
    int monotoneIncreasingDigits(int n) {
        string N = to_string(n);
        int flag = N.size();//记录从哪里开始改
        //不能从前往后遍历，不然会改变已经排好的数，比如339
        //从后往前遍历
        for(int i = N.size() - 1; i > 0; i--)
        {
            //如果左边的数大于右边的数了
            if(N[i - 1] > N[i])
            {
                N[i - 1] -= 1;
                flag = i;
            }

        }
        //将flag之后的所有数字变为9
        for(int i = flag; i < N.size(); i++)
        {
            N[i] = '9';
        }
        return stoi(N);
    }
};

    这道题利用贪心算法，有几点需要注意：

• 原题目中相等的数也算递增，我忽略了这一点

• 在遍历过程中需要从后往前遍历，去寻找最靠前的需要退位的数字，我自己开始写的时候，从前往后遍历了，导致出错，339这个成了329，这是不行的

• 用字符串存数字也挺简单的，不一定非得把数存在整型数组里

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

class Solution {
public:
    //贪心，要分三种情况
    int maxProfit(vector<int>& prices, int fee) {
        int result = 0;//记录利润
        int minPrice = prices[0];//记录最小价格，用于计算买卖后的利润
        for(int i = 0; i < prices.size(); i++)
        {
            //判断是否要买入，如果价格低，那么minprice就是买入时的价格，只要不买，可以一直更新的
            if(prices[i] < minPrice) minPrice = prices[i];
            //判断是否卖出,如果当前价格比最小价格+手续费还低，那么不卖
            else if(prices[i] <= minPrice + fee)
            {
                continue;
            }
            else//此时要考虑卖掉
            {
                result += prices[i] - minPrice - fee;
                //因为不确定这次价格是否为这个区间内最高的价格
                //所以要将minPrice置为暂时卖掉的钱-fee，
                minPrice = prices[i] - fee;
            }
            
        }
        return result;
    }
};

    这道题考虑买入卖出的时机，分三种情况：

• 要买：当前价格小于最低价格，更新价格；

• 不卖：如果当前价格高于最低价格但又低于最低价格+手续费；

• 要卖：如果当前价格高于最低价格+手续费，卖掉当前股票，并更新最低价格。

注意：

    当卖掉时，可能只是暂时卖掉，因为有可能此时不是价格区间中最高的价格，所以最低价格要减手续费，这样，当下一个价格高于 minPrice+fee时，就像等于高于上一个股票的原价，那么利润增加价格差，正好手续费也消掉了。

    不得不说，这个代码随想录的贪心算法思路还是很巧妙的，挺难想到的。