贪心

分发饼干

两个数组，一个是饼干，一个是胃口，保证；饼干大于等于胃口的前提下，计算能满足的最大数值。

• 思路： 保证局部最优，其实没什么固定套路，就是大饼干对应大胃口，这样就不会造成浪费。

摆动序列

给一数组，计算该数组中满足摆动的最长子序列的长度，摆动就是差值一正一负

• 思路：遇到前后差值一正一负就可以增加最长子序列。

最大子数组和

给整数数组，计算出连续的子序列的最大值

• 思路： 如果和为负数或为0，就从下一个索引处重新开始。
  

买卖股票的最佳时机

给整数数组，数组表示每天的股票价格，求最大利润

• 思路：就是统计差值为正的情况，所以可以忽略区间，只需要求出差值然后将正值相加即可。

跳跃游戏

给一个非负整数数组，数组内的值是可以跳跃的最大步伐，从第一个下标开始，是否能够跳到最后一个数组。

• 思路：其实问题就是覆盖范围是否能够将数组长度覆盖，所以只需要在覆盖范围内遍历，然后不断更新覆盖范围，判断如果覆盖范围大于等于数组长度
  ，说明就可以跳跃。

跳跃游戏2

这次是求到达数组最后的最小的步数

• 思路：每次走最大步数，然后在最大步数处，步伐加一且更新最大步数，因为是一定可以到达终点的，所以可以这样考虑。

k次数取反后最大化数组和

给一个数组，将数组中的元素按照k次取反，可以重复取反

• 思路：按照绝对值排序，然后从前到后也就是优先将绝对值大的负数转正，多余的k次数就用在绝对值最小的值身上

加油站

给两个数组，一个代表加到的油，一个代表消耗的油，如果能循环上路，返回起始的加油站编号，如果不能，就返回-1

• 思路： 从0开始，计算出油箱内的剩余油量，如果油量剩余小于0，那就说明在这个区间内，无论从哪个点开始，都会在这里油量小于0，
  所以从i+1处重新计算，直到遍历完所有数组。因为如果判断总消耗小于等于总加入，那么可以循环一圈。

分发糖果

n个小孩，按照评分分糖果，要求是评分比身边两位高的，糖果也要比他们至少高一个。

• 思路：依此左右遍历，然后每个人分的糖果值取最高值。

柠檬水找零

5，10，20 的账单保证每位顾客都能找零；

• 思路：模拟找零过程，优先将10找零出去。

根据身高重建队列

每个人有一个数组，数组第一个元素表示身高，第二个元素表示前面有多少人身高大于等于自己。重新排列，使这种组合成立。

• 思路： 和分糖果一样，有两个条件要考虑，所以依此进行考虑，先按照身高从大到小排序，然后再按照位数进行插入，这样就能保证
  位数的正确。

用最少箭数射掉气球

提供气球的起始结束坐标，气球尺寸相同，当箭射中气球中间的位置就能射掉气球，因此当多个气球范围重叠，可以用一支箭射爆，求最少箭数

• 思路：当气球的结束位置大于下一个气球的开始位置，那就是气球重叠，所以将气球进行排序，然后当气球重叠时候，可以将这些气球并为一起，
  意思就是这些气球的结束位置就是它们的最小的位置，当不重叠时候，就射出一支箭。

无重叠区间

求出移除几个数组后，剩余的区间不会重叠

• 思路 与气球问题类似，只不过当边界相等时候，不算重叠

划分字符区间

给定一个字符串，划分字符串，使同一字母出现在一个字符串中，返回各个字符串的长度

• 思路：先遍历字符串，记录每个字母最远的下标，然后重新遍历，设置字符最大边界，每次更新为出现过的字母的最远下标，当当前
  下标等于最远下标的时候，就是分割的时候，记录字符长度。

合并区间

还是扎气球问题，只不过判断重叠后，要做的是将区间重叠并返回。

单调递增的数字

返回小于该数字的最大递增数字

• 思路：将数字转换为字符串存入字符数组中，从后开始遍历，当前一位的数字大于后一位时，前一位减一，后一位变9，这里可以先不着急变9，而是记录变9的开始坐标
  ，之后重新遍历，将后面的字符全部转换为9。