摆动数列
求摆动 子序列 的 最大长度 问题：
- 摆动子序列 ：如何衡量是否摆动
- 最大长度：如何遍历一遍找到最大长度
解决思路：
- 记录上两个数之间的差值，规定等于 i -（i+1），大于零则为上坡，小于零则为下坡，若能保持上下坡交替关系期间的子序列为 摆动子序列。
- 由此可以看出必须使用两个变量a， b 一个记录上一段坡度是否与当前坡度【相反】
- 没做出来之前一直执着于用一个变量记录，发现搞得非常混乱，因为当前坡度为可能有三种情况 >0, <0, ==0 而上一个坡度
- 假若抛弃前面段选出的的摆动子序列，而后几段的更短，则无法找到之前放弃记录的数据，用数组保存太占空间，可以选用 常数 保存，一直比较让该变量只记录最大值
class Solution { public int wiggleMaxLength(int[] nums) { int n = nums.length; if (n<2) return n; int preDiff = nums[0] - nums[1]; // 第一个坡度 int ret = (preDiff != 0) ? 2 : 1; // 取不取第二个数取决于第一个坡度是否为0 // 从第二个坡度开始遍历（第一个坡度已算出） for (int i=2; i<n ; i++){ // 第二个坡度 int diff = nums[i-1] - nums[i]; // 出现升降坡度情况则保存当前数字 if ((diff>0 && preDiff<=0) || (diff<0 && preDiff>=0)){ ret++; // 更新坡度 preDiff = diff; // 注意这里，只在摆动变化的时候更新prediff } } return ret; } }跳跃游戏–步数抽象化
- 使能向前的步数覆盖的范围尽可能的大
- 用最少的步数增大覆盖范围
跳跃游戏Ⅱ
贪心思路：在最大跳跃覆盖范围内跳到此范围内能使_下一个覆盖范围最大_的点上i 具体实现：
- 范围控制：如何找到该范围内最大的跳转点i，并只在此时让步数ans++
- 利用当前覆盖最远范围当作右边界，左边界无视，数组只需一直向前遍历即可
- 当遍历达到右边界时转跳点随之确定（范围内结束），此时更新当前最大覆盖范围，并使ans++
- nextDistance不需要每次清零是因为，nextDis的值不止由nums[i]的数值确定，还由当前下标决定，需要清零的范围已超出i原本的触及范围。
启示： 要控制一个变量阶段性确定为一个值但这个值在反复跳转时，可以考虑用一个暂时变量next/pre/temp 代替该变量变化，最后再赋值给该变量。
// 版本一
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() == 1) return 0;
int curDistance = 0; // 当前覆盖最远距离下标
int ans = 0; // 记录走的最大步数
int nextDistance = 0; // 下一步覆盖最远距离下标
for (int i = 0; i < nums.size(); i++) {
nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖最远距离下标
if (i == curDistance) { // 遇到当前覆盖最远距离下标
if (curDistance != nums.size() - 1) { // 如果当前覆盖最远距离下标不是终点
ans++; // 需要走下一步
curDistance = nextDistance; // 更新当前覆盖最远距离下标（相当于加油了）
if (nextDistance >= nums.size() - 1) break; // 下一步的覆盖范围已经可以达到终点，结束循环
} else break; // 当前覆盖最远距离下标是集合终点，不用做ans++操作了，直接结束
}
}
return ans;
}
};
加油站（找起点问题）
- 从起始点到终点整个过程中邮箱里的油量不能<0 ， 一旦小于零即中断，所以可以局部油量剩余判断该点能否作为起始点
- 所以一遇到起始点到当前油箱内余量<0的情况时立即更换起始点为i+1，且重新开始计算curSum = 0；
- 其他问题：
- 倘若在选定区间内可以有另一点使得curSum > 0呢？即这种选择起点的局部方法是否存在问题？
- 如何判断当前能否走完一圈，应当返回-1还是找到的起点start
柠檬水找零–找零问题
身高排队问题
想如何确定一个维度，然后再按照另一个维度重新排列 （套路）：一般这种数对，还涉及排序的，根据第一个元素正向排序，根据第二个元素反向排序，或者根据第一个元素反向排序，根据第二个元素正向排序，往往能够简化解题过程。
class Solution {
public int[][] reconstructQueue(int[][] people) {
LinkedList<int[]> que = new LinkedList();
Arrays.sort(people, (a, b)->{
if (a[0] == b[0]) return a[1] - b[1]; // 人数按默认从小到大
return -(a[0]-b[0]); // 身高按从大到小
});
for (int[] p:people){
que.add(p[1], p); // 将k=i 的数插入i位置
// people数组此时已经按照身高大到小排列，但站位不一定符合前k个人关系
// 此时按照k插入：后边未排序的、k较小的数插入前面已经排好的数内，不会有任何新问题
// 因为只要在该k之前的数都一定 >= 该数，不会使得已经排好的位置发生错误，
// 在之前已排好高矮的前提下按k的大小插入新链表即可
}
return que.toArray(new int[people.length][]);
}
}
划分字母区间
class Solution {
public List<Integer> partitionLabels(String s) {
int[] alph = new int[26]; // 对应26个字母的字典
for (int i=0;i<s.length();i++){
int j = s.charAt(i) - 'a';
alph[j] = i; // 更新最后一次出现的位置
}
List<Integer> res = new ArrayList();
int R = 0;
int last = -1; // 左开右闭区间
for (int i=0;i<s.length();i++){
R = Math.max(R, alph[s.charAt(i) - 'a']);
if (i == R){
res.add(i-last);
last = R;
}
}
return res;
}
}
738. 单调递增的数字
:::tips
题目描述：当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。 给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
:::
贪心思路
最大的数字 –> 相邻的两个数，前一位数减一， 此时比原先的数小的最大的数为 后一位数顶到 9
所以此时若为不单调的数字序列， 从_不单调的高位到低位满足：从不单调的数 -1，之后的数全变成9_
int n = 1234;
// 把整数拆分为-->单独的个位数的数字
String s = String.valueOf(n);
char[] chars = s.toCharArray();
// 把整数char集合转变为一个整数
Integer.parseInt(String.valueOf(chars));
