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;}
};