算法训练（leetcode）第二十三天 | 455. 分发饼干、*376. 摆动序列、53. 最大子数组和

455. 分发饼干

leetcode题目地址

贪心，两个数组排序，从前向后或从后向前均可，二者需保持同序，使用两个指针分别指向两个数组，当胃口满足时两个指针同时后移并计数，若不满足则饼干指针后移寻找合适的饼干。

由于使用了两次快排，所以时间复杂度为O(nlogn)。

时间复杂度： $O(nlogn)$
空间复杂度： $O(1)$

// c++
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int cnt=0;
        int i=0, j=0;
        while(i<g.size() && j<s.size()){

            if(j<s.size() && s[j]>=g[i]) { // 满足胃口
                cnt++;
                i++;
            }
            // 不管是否满足胃口  饼干都后移
            // 1. 满足胃口 当前饼干已使用 所以后移
            // 2. 不满足胃口  当前饼干小于当前胃口 后移找符合胃口的饼干
            j++;
            
        }
        return cnt;
    }
};

*376. 摆动序列

leetcode题目地址

保证前后差值一正一负即可。

有一个问题还没搞清楚，如果使用当前子序列的最后一个元素和当前元素求差（代码中注释掉的写法）则会不通过，这里没有搞清楚是什么原因。。。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// c++
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        bool flag = true;
        if(nums.size()<2) return nums.size();
        // int pre = nums[0];
        int prediff = 0;
        int curdiff = 0;
        int cnt = 1;
        for(int i=1; i<nums.size(); i++){
        	// curdiff = nums[i] - pre;
            curdiff = nums[i] - nums[i-1];
            if(curdiff==0) continue;
            if((prediff>=0&&curdiff<0)||(prediff<=0&&curdiff>0)){
                cnt++;
                // pre = nums[i];
                prediff = curdiff;
            }
        }
        return cnt;

    }
};

53. 最大子数组和

leetcode题目地址

贪心策略，只要当前和为负就舍弃，因为负数再加后边的数只会让后边的和变小。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// c++
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum=0;
        int maxsum=nums[0];
        for(int i=0; i<nums.size(); i++){
            sum+=nums[i];
            if(sum>maxsum) maxsum=sum;
            if(sum<0) sum=0;
        }
        return maxsum;
    }
};