為了滿足更多的小孩，就不要造成餅干尺寸的浪費(fèi)

大尺寸的餅干既可以滿足胃口大的孩子也可以滿足胃口小的孩子，那么就應(yīng)該優(yōu)先滿足胃口大的

這里的局部最優(yōu)就是大餅干喂給胃口大的，充分利用餅干尺寸喂飽一個(gè)，全局最優(yōu)就是喂飽盡可能多的小孩

可以嘗試使用貪心策略，先將餅干數(shù)組和小孩數(shù)組排序。

然后從后向前遍歷小孩數(shù)組，用大餅干優(yōu)先滿足胃口大的，并統(tǒng)計(jì)滿足小孩數(shù)量

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int index = s.size() - 1; // 餅干數(shù)組的下標(biāo)int result = 0;for (int i = g.size() - 1; i >= 0; i--) { // 遍歷胃口if (index >= 0 && s[index] >= g[i]) { // 遍歷餅干result++;index--;}}return result;}
};

• 時(shí)間復(fù)雜度：O(nlogn)
• 空間復(fù)雜度：O(1)

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int prediff = 0;int curdiff = 0;int result = 1;for(int i = 0; i < nums.size() - 1; i++){curdiff = nums[i + 1] - nums[i];if((prediff >= 0 && curdiff < 0) || (prediff <= 0 && curdiff> 0)){prediff = curdiff;result++;}}return result;}
};

1. 時(shí)間復(fù)雜度：O(n)
2. 空間復(fù)雜度：O(n)

注意兩點(diǎn)：

1. 什么時(shí)候選擇起始位置？遇到負(fù)數(shù)就停止？還是和為負(fù)數(shù)就停止？

• 遇到負(fù)數(shù)的時(shí)候不應(yīng)該停止，因?yàn)楹竺婵赡苡懈蟮恼龜?shù)可加
• 當(dāng)和為負(fù)數(shù)的時(shí)候就該停止了，因?yàn)檫@個(gè)負(fù)數(shù)只會(huì)拖累后面的數(shù)
• 可以用result來記錄最大值

2. result的最小值應(yīng)該初始化為什么？初始化為0嗎？那如果數(shù)組中只有負(fù)數(shù)怎么辦？

• 因此，result應(yīng)該初始化為無窮小

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT_MIN;int count = 0;for(int i = 0; i < nums.size(); i++){count += nums[i];result = count > result ? count : result;if(count < 0){count = 0;}}return result;}
};