贪心算法（四）

4.更多练习题

4）力扣https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/这道题运用贪心算法，就是每天只考虑与前一天的差价，只要差价大于零，从局部最优来考虑，就应该卖出前一天的股票。这样可以得到全局最优解。

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

5）

力扣https://leetcode.cn/problems/queue-reconstruction-by-height/这道题 的第二个属性指的是有多少比自己高，所以可以按照身高由高到低来重建队列。

处理当前元素时，插入的位置就是第二个属性的值，因为之前插入的人都比自己高。

另外，身高相同时，第二个元素值小的人，先进行插入。

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(),
        [&](vector<int>& a, vector<int>& b){
            if(a[0]==b[0] ) return a[1]<b[1];
            return a[0]>b[0];
        }
        );

        vector<vector<int>> res;
        for(auto p : people){
            res.insert(res.begin()+p[1], p);
        }
        return res;

    }
};

6)力扣https://leetcode.cn/problems/non-decreasing-array/当出现第i个元素小于第i-1个元素时，有两种修改方法：

一是令第i个元素等于第i-1个元素

二是令第i-1个元素等于第i个元素

这样局部保证了非递减，而且对数列中其他元素影响最小。

贪心算法的运用在于，既然发现了局部的递减，那就立刻进行修改，因为只能修改一次，所以修改完再判断整个数列是否完全非递减，若满足则成功，若不满足则表示数列不符合题目要求。

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int n = nums.size();
        for(int i=1;i<n;i++){
            if(nums[i]<nums[i-1]){
                int t = nums[i];
                nums[i] = nums[i-1];
                if(judge(nums)){
                    return true;
                }else{
                    nums[i] = nums[i-1] = t;
                    return judge(nums);
                }
            }
        }
        return true;
    }

    bool judge(vector<int>& nums){
        int n = nums.size();
        for(int i=1;i<n;i++){
            if(nums[i]<nums[i-1]){
                return false;
                }
        }
        return true;
    }
};