47.哀家要长脑子了！

1.

贪心不知道怎么贪。。。每个为选择最大的，如果前一位比后一位大，就要把前一位减去1，因为要最大的嘛，一点点减，然后剩下的都变为9，因为要最大的嘛！

C++版

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string arr = to_string(n);
        int max = -1, idx = 0;
        for(int i = 0; i < arr.size()-1; i++) {
            if(max <= arr[i]) {
                max = arr[i];
                idx = i;
            }

            if(arr[i] > arr[i+1]) {
                arr[idx] -= 1;
                for(int j = idx+1; j < arr.size(); j++) {
                    arr[j] = '9';
                }
               
            }   
        }
        return stoi(arr);
    }
};

Java版本 

class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] t = (n + "").toCharArray();
        int max = -1, idx = -1;
        for(int i = 0; i < t.length-1; i++) {
            if(max < t[i]) {
                max = t[i];
                idx = i;
            }

            if(t[i] > t[i+1]) {
                t[idx] -=1;
                for(int j = idx+1; j < t.length; j++) {
                    t[j] = '9';
                } 
            }
        }
        return Integer.parseInt(new String(t));
    }
}

 2.

贪心怎么贪，每次选择的股票使得收获得利润最大。那么当后面的股票比前面的股票大的时候就可以卖出去，这样子积累下来的利润就是最大利润。

C++版

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for(int i = 1; i < prices.size(); i++) {
            if(prices[i] > prices[i-1]) {
                int dif = prices[i] - prices[i-1];
                res += dif;
            }
        }
        return res;
    }
};

Java版

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int res = 0;
        for(int i = 1; i < n; i++) {
            if(prices[i] - prices[i-1] > 0) {
                int t = prices[i] - prices[i-1];
                res += t;
            }
        }
        return res;
    }
}

3.

要交手续费，交！设定买入股票的时候交手续费。需要注意的是当卖出股票时，买入下一支股票时，更新为股票的价格而不用加上手续费，要不然买的话会加上两次手续费

C++版

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        // 买入股票的时候交手续费
        int buy = prices[0] + fee;
        int res = 0;
        for(int i = 1; i < prices.size(); i++) {
            // 说明此时买入第i支股票所用的成本更少
            if(prices[i] + fee < buy) {
                buy = prices[i] + fee;
            }
            // 此时卖出股票可以盈利
            else if(prices[i] > buy) {
                // 利润累加 这里面包含了手续费
                res += prices[i] - buy;
                // 更新买入股票的成本 如果要买这支股票的话 后续的if会加上手续费
                buy = prices[i];
            }
        }
        return res;
    }
};

Java版

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int res = 0;
        int buy = prices[0] + fee;
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] + fee < buy) 
                buy = prices[i] + fee;
            else if(prices[i] > buy) {
                res += prices[i] - buy;
                buy = prices[i];
            }
        }
        return res;
    }
}

哎呀，烦死了！！！！！！！！！！！！！我根本都想不出！！烦死啦！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！