455. 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
-
把孩子的胃口排序，先看胃口最大的孩子可不可以得到满足
-
把饼干排序，如果孩子的最大所需小于等于最大饼干，直接把最大饼干分给胃口最大的孩子。
class Solution {
public int findContentChildren(int[] g, int[] s) {
if(s.length==0){
return 0;//饼干都没有 满足谁？
}
Arrays.sort(g);//给孩子的胃口从小到大排序
Arrays.sort(s);//给饼干按从小到大的顺序排序
int count = 0;//满足孩子的个数
for (int i = g.length-1; i>=0; i--) {
// 遍历孩子的胃口
for (int j = s.length-1; j >=0; j--) {
// 遍历每一块饼干
if(g[i]<=s[j]){
count++;//如果找到可以满足孩子胃口的饼干，饼干++
s=delete(s,j);//删除该饼干并更新饼干数组
break;
}
}
}
return count;
}
// 删除数组中元素的做法
private int[] delete(int[] s, int index) {
for (int i = index; i < s.length-1; i++) {
s[i] = s[i+1];
}
return Arrays.copyOf(s, s.length - 1);
}
}
376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
保持区间波动，只需要把单调区间上的元素移除就可以了
class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums.length==1){
return 1;//一个元素的序列也视为摆动序列
}
int preDiff = 0;
int curDiff = 0;
int count = 1;
for(int i = 1;i<nums.length;i++){
curDiff = nums[i]-nums[i-1];//当前的差值
if(curDiff>0&&preDiff<=0 || curDiff<0&&preDiff>=0){//满足摆动序列的条件
count++;
preDiff = curDiff;//注意这行要放在if里面
}
}
return count;
}
}
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
-
计算起点的时候，一定是从正数开始计算，因为负数只会拉低总和
-
当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小
-
如果数组中根本就没有正数，那么数组中的最大值即为所求
class Solution {
public int maxSubArray(int[] nums) {
int sum = Integer.MIN_VALUE;
int result = Integer.MIN_VALUE;
//先遍历数组，求出数组中的最大值
for(int i = 0;i<nums.length;i++){
result = Math.max(nums[i],result);//求取数组最大值
}
if(result<=0){
return result;//数组中没有正数，返回数组的最大值
} else {
result = Integer.MIN_VALUE;//数组中有正数的话，那还有的盘，重置result
}
//下面是数组中有正数的情况
for(int i = 0;i<nums.length;i++){
//从正数开始遍历
if(nums[i]<=0 && sum==Integer.MIN_VALUE){
continue;
}
if(sum==Integer.MIN_VALUE){
sum = nums[i];//开始遍历的位置
result = Math.max(result,sum);//每加一个数，都更新最大和
} else{
sum += nums[i];//
result = Math.max(result,sum);//每加一个数，都更新最大和
}
if(sum<0){
sum = Integer.MIN_VALUE;//连续和为负数，立刻放弃，并重置sum
continue;
}
}
return result;
}
}