算法训练（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;}
};