代码随想录day31

455. 分发饼干

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int result = 0;
        int index = s.size() - 1;
        for (int i = g.size() - 1; i >= 0; i--) {
            if (index >= 0 && s[index] >= g[i]) {
                index--;
                result++;
            }
        }
        return result;
    }
};

376. 摆动序列

贪心算法：

 1 class Solution {
 2 public:
 3     int wiggleMaxLength(vector<int>& nums) {
 4         if (nums.size() <= 1) return nums.size();
 5         int curDiff = 0;//记录当前的差值
 6         int preDiff = 0;//记录前一对差值
 7         int result = 1; //记录峰值个数
 8         for (int i = 0; i < nums.size() - 1; i++) {
 9             curDiff = nums[i + 1] - nums[i];
10             if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
11                 result++;
12                 preDiff = curDiff;
13             }
14         }
15         return result;
16     }
17 };

53. 最大子数组和

贪心算法：

 1 class Solution {
 2 public:
 3     int maxSubArray(vector<int>& nums) {
 4         int result = INT32_MIN;
 5         int count = 0;
 6         for (int i = 0; i < nums.size(); i++) {
 7             count += nums[i];
 8             result = count > result ? count : result;
 9             if (count < 0) {
10                 count = 0;
11                 continue;
12             }
13         }
14         return result;
15     }
16 };