贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

唯一的难点就是如何通过局部最优，推出整体最优。

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

分发饼干

描述：

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例：

示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1 解释:你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。

示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出2.

思路：

大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

也可以换一个思路，小饼干先喂饱小胃口。

解法：

var findContentChildren = function(g, s){
    let idx1 = 0, idx2 = 0;
    let sum = 0;
    g.sort((a,b)=>a-b);
    s.sort((a,b)=>a-b);
    while(idx1<s.length){
        if(s[idx1]>=g[idx2]){
            idx2++;
            sum++;
        }
        idx1++;
    }
    return sum;
}

摆动序列

描述：

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。

少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例：

示例 1:
输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。

示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

示例 3:
输入: [1,2,3,4,5,6,7,8,9]
输出: 2

思路：

​ 局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

​ 实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）。这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点。

​ 说的好听，其实就是计算上升下降的次数

解法：

var wiggleMaxLength = function(nums){
    if(nums.length<=1)
        return nums.length;
    // 因为少于两个元素的序列也是摆动序列
    let res = 1;
    let preDiff = 0;
    let curDiff = 0;
    for(let i=0;i<nums.length-1;i++){
        curDiff = nums[i+1]-nums[i];
        if((curDiff>0&&preDiff<=0)||(curDiff<0&&preDiff>=0)){
            res++;
            preDiff = curDiff;
        }
    }
    return res;
}

最大子序和

描述：

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

输入: [-2,1,-3,4,-1,2,1,-5,4] 
输出: 6 
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路：

​ 计算起点的时候，一定是从正数开始算起，因为负数只会拉低总和。当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

解法：

var maxSubArray = function(nums){
    let res = -Infinity;
    let count = 0;
    for(let i=0;i<nums.length;i++){
        count += nums[i];
        if(count > res)
            res = count;
        if(count<0)
            count = 0;
    }
    return res;
}

买卖股票的最佳时机ii

描述：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例：

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

思路：

如果想到其实最终利润是可以分解的，那么本题就很容易了！

如何分解呢？假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！

其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。

相当于只有后一天-前一天>0的时候才回买入卖出

解法：

var maxProfit = function(prices){
    let res = 0;
    for(let i=1;i<prices.length;i++)
        res += Math.max(prices[i]-prices[i-1], 0);
    return res;
}

跳跃游戏

描述：

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

示例：

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

思路：

其实跳几步无所谓，关键在于可跳的覆盖范围！不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。这个范围内，别管是怎么跳的，反正一定可以跳过来。

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

解法：

var canJump = function(nums){
    if(nums.length===1)
        return true;
    let cover = 0;
    /*
        i每次移动只能在cover的范围内移动，每移动一个元素，
        cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。
        而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。
    */
    for(let i=0;i<=cover;i++){
        // i表示上一个覆盖范围所涉及的区域，nums[i]表示当前元素所涉及的覆盖区域
        cover = Math.max(cover, i+nums[i]);
        if(cover>=nums.length-1)
            return true;
    }
    return false;
}

跳跃游戏II

描述：

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例：

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明: 假设你总是可以到达数组的最后一个位置。

思路：

​ 局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。

​ 思路虽然是这样，但在写代码的时候还不能真的就能跳多远跳远，那样就不知道下一步最远能跳到哪里了。

​ 所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！

需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

解法：

var jump = function(nums){
    let curIndex = 0;
    let cover = 0;
    let steps = 0;
    for(let i=0;i<nums.length-1;i++){
        cover = Math.max(cover, i+nums[i]);
        if(i===curIndex){
            curIndex = cover;
            steps++;
        }
    }
    return steps;
}

K次取反后最大化的数组和

描述：

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
以这种方式修改数组后，返回数组可能的最大和。

示例：

示例 1：
输入：A = [4,2,3], K = 1
输出：5
解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。

示例 2：
输入：A = [3,-1,0,2], K = 3
输出：6
解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。

示例 3：
输入：A = [2,-3,-1,5,-4], K = 2
输出：13
解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。

思路：

​ 让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

​ 如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。

解法：

var largestSumAfterKNegative = function(nums, k){
    nums.sort((a,b)=>Math.abs(b)-Math.abs(a));
    for(let i=0;i<nums.length;i++){
        if(nums[i]<0&&k>0){
            nums[i] *= -1;
            k--;
        }
    }
    // 剩余k是奇数，那么还需要反转
    if(k>0&&k%2===1)
        nums[nums.length-1] *= -1;
    // 剩余k是偶数，则反转与不反转没有区别，所以不用进行反转
    return nums.reduce((a,b)=>a+b);
}

加油站

描述：

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:
如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。

示例：

示例 1: 
输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3 
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2: 
输入:
gas = [2,3,4]
cost = [3,4,3]
输出: -1
解释: 你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油。开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油。开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油。你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。因此，无论怎样，你都不可能绕环路行驶一周。

思路：

​ 如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。每个加油站的剩余量rest[i]为gas[i] - cost[i]。

​ i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。

解法：

var canCompleteCircuit = function(gas, cost){
    const gasLen = gas.length;
    let start = 0;
    let curSum = 0;
    let totalSum = 0;
    for(let i=0;i<gasLen;i++){
        curSum += gas[i] - cost[i];
        totalSum += gas[i] - cost[i];
        if(curSum<0){
            curSum = 0;
            start = i+1;
        }
    }
    if(totalSum<0)
        return -1;
    return start;
}

分发糖果

描述：

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
- 每个孩子至少分配到 1 个糖果。
- 相邻的孩子中，评分高的孩子必须获得更多的糖果。

示例：

示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

思路：

先确定右边评分大于左边的情况（也就是从前向后遍历），再确定左孩子大于右孩子的情况（从后向前遍历）。

解法：

var candy = function(ratings){
    let candys = new Array(ratings.length).fill(1);
    // 从左往右看，右边是否比左边高，高就右边+1，否则取1
    for(let i=1;i<ratings.length;i++)
        if(ratings[i]>ratings[i-1])
            candys[i] = candys[i-1]+1;
    // 从右往左看，左边是否比右边高，高就左边取最大值，否则取1
    for(let i=ratings.length-2;i>=0;i--)
        if(ratings[i]>ratings[i+1])
            candys[i] = Math.max(candys[i], candys[i+1]+1);
    let count = candys.reduce((a,b)=>a+b);
    return count;
}

柠檬水找零

描述：

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例：

示例 1：
输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：
输入：[5,5,10]
输出：true

示例 3：
输入：[10,10]
输出：false

示例 4：
输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

思路：

有如下三种情况：

• 情况一：账单是5，直接收下。
• 情况二：账单是10，消耗一个5，增加一个10
• 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

解法：

var lemonadeChange = function(bills){
    let fiveCount = 0;
    let tenCount = 0;
    for(let i=0;i<bills.length;i++){
        let bill = bills[i];
        if(bill===5)
            fiveCount++;
        else if(bill===10){
            if(fiveCount>0){
                fiveCount--;
                tenCount++;
            }else
                return false;
        }else {
            // 根据贪心算法的原则，这里应该是有大钱就先用大钱
            if(tenCount>0&&fiveCount>0){
                tenCount--;
                fiveCount--;
            }else if(fiveCount>=3)
                tenCount-=3;
            else
                return false;
        }
    }
    return true;
}

根据身高重建队列

描述：

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例：

示例 1：
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

思路：

按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。

此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！而后只需要按照k为下标重新插入队列就可以了。

解法：

var reconstructQueue = function(people){
    let queue = [];
    people.sort((a,b)=>{
        if(b[0]!==a[0])
            return b[0] - a[0];
        else
            return a[1] - b[1];
    })
    for(let i=0;i<people.length;i++)
        // splice: index、howmany、item1...itemx
        // index：从何处添加/删除元素；howmany：删除多少元素
        queue.splice(people[i][1], 0, people[i]);
    return queue;
}

用最少数量的箭引爆气球

描述：

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

示例：

示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4

示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2

示例 4：
输入：points = [[1,2]]
输出：1

示例 5：
输入：points = [[2,3],[2,3]]
输出：1

思路：

​ 局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。

​ 为了让气球尽可能的重叠，需要对数组进行排序。

​ 按照气球的起始位置排序。既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。

​ 从前向后遍历遇到重叠的气球了怎么办？如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。

​ 这个图说明了代码中为什么points[i] [1] = Math.min(points[i-1] [1], points[i] [1])，而不是Math.max。

解法：

var findMinArrowShots = function(points){
    points.sort((a, b)=>a[0]-b[0]);
    let result = 1;
    for(let i=1;i<points.length;i++){
        if(points[i][0]>points[i-1][1])
            result++;
        else
            // 可以标记已经射爆的气球，而不用从数组中删除气球
            points[i][1] = Math.min(points[i-1][1], points[i][1]);
    }
    return result;
}

无重叠区间

描述：

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例：

示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

思路：

按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

此时问题就是要求非交叉区间的最大个数。

右边界排序之后，局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优：选取最多的非交叉区间。

解法：

var eraseOverlapIntervals = function(intervals){
    // 按照左边界升序排列
    intervals.sort((a,b)=>a[0]-b[0]);
    let count = 1;
    let end = intervals[intervals.length-1][0];
    // 倒序遍历，对单个区间来说，左边界越大越好，因为给前面区间的空间越大
    for(let i=intervals.length-2;i>=0;i--)
        if(intervals[i][1]<=end){
            count++;
            end = intervals[i][0];
        }
    // count 记录的是最大非重复区间的个数
    return intervals.length - count;
}

划分字母区间

描述：

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8] 
解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

提示：
S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' 。

思路：

​ 在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

解法：

var partitionLabels = function(s){
    let hash = {};
    for(let i=0;i<s.length;i++)
        // 记录当前字母能到达的最远下标
        hash[s[i]] = i;
    let res = [];
    let left = 0;
    let right = 0;
    for(let i=0;i<s.length;i++){
        // 上一个字母的最右侧与当前字母的最右侧之间的对比
        // 一个字母最多能在一段中
        right = Math.max(right, hash[s[i]]);
        if(right===i){
            res.push(right-left+1);
            left = i+1;
        }
    }
    return res;
}

合并区间

描述：

给出一个区间的集合，请合并所有重叠的区间。

示例：

示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]

示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间

思路：

​ 按照左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优：合并所有重叠的区间。

解法：

var merge = function(intervals){
    intervals.sort((a,b)=>a[0]-b[0]);
    let prev = intervals[0];
    let result = [];
    for(let i=0;i<intervals.length;i++){
        let cur = intervals[i];
        if(cur[0]>prev[1]){
            result.push(prev);
            prev = cur;
        }else
            prev[1] = Math.max(cur[1], prev[1]);
    }
    result.push(prev);
    return result;
}

单调递增的数字

描述：

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的）

示例：

示例 1:
输入: N = 10
输出: 9

示例 2:
输入: N = 1234
输出: 1234

示例 3:
输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

思路：

​ 局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]–，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。全局最优：得到小于等于N的最大单调递增的整数。

​ 局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9。

​ 从前向后遍历会改变已经遍历过的结果，从后向前遍历可以利用上次比较得出的结果。

解法：

var monotoneIncreasingDigits = function(n){
    n = n.toString();
    n = n.split('').map(item=>{
        return +item;
    });
    let flag = Infinity;
    for(let i=n.length-1;i>0;i--){
        if(n[i-1]>n[i]){
            flag = i;
            n[i-1] = n[i-1]-1;
            n[i] = 9;
        }
    }
    // 标记从哪一位开始统一改成9
    for(let i=flag;i<n.length;i++)
        n[i] = 9;
    n = n.join('');
    return +n;
}

买卖股票的最佳时机含手续费

描述：

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例：

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2 
输出: 8
解释: 能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

思路：

​ 本题有了手续费，就要关系什么时候买卖了，因为计算所获得利润，需要考虑买卖利润可能不足手续费的情况。如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。

​ 此时无非就是要找到两个点，买入日期，和卖出日期。

• 买入日期：其实很好想，遇到更低点就记录一下。
• 卖出日期：这个就不好算了，但也没有必要算出准确的卖出日期，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。

解法：

var maxProfit = function(prices, fee){
    let result = 0;
    let minPrice = prices[0];
    for(let i=1;i<prices.length;i++){
        if(prices[i]<minPrice)
            // 找最低的价格买入
            minPrice = prices[i];
        if(prices[i]>=minPrice&&prices[i]<=minPrice+fee)
            continue;
        if(prices[i]>minPrice+fee){
            result += prices[i]-minPrice-fee;
            // !!!这句话很重要
            minPrice = prices[i]-fee;
        }
    }
    return result;
}

监控二叉树

描述：

给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

示例：

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点

思路：

​ 头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

​ 节点有三种状态：节点有摄像头、节点有覆盖、节点无覆盖。空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了

解法：

var minCameraCover = function(root){
    let result = 0;
    /**
     节点的状态值：
       0 表示无覆盖 
       1 表示有摄像头
       2 表示有覆盖 
    后序遍历，根据左右节点的情况,来判读 自己的状态
     */
    function traversal(cur){
        // 空节点是有覆盖的状态，否则叶子节点就需要一个摄像头了
        if(!cur)
            return 2;
        let left = traversal(cur.left);
        let right = traversal(cur.right);
        if(left===2&&right===2)
            return 0;
        if(left===0||right===0){
            result++;
            return 1;
        }
        if(left===1||right===1)
            return 2;
        return -1;
    }
    // 这个别忘了
    if(traversal(root)===0)
        result++;
    return result;
}

相似的题目

• 需要排序：根据身高重建队列、用最少数量的箭引爆气球、无重叠区间（左边界升序排列，从后向前遍历）、合并区间
• 区间：划分字母区间、跳跃游戏、跳跃游戏II
• 从左边和右边分别进行考虑：单调递增的数字(从后向前遍历)、分发糖果
• 买卖股票的最佳时机含手续费、买卖股票的最佳时机ii、最大子序和、加油站
• 摆动序列、合并区间

总结：

• 可能需要对区间进行排序，对左区间排序还是右区间排序需要进一步考虑
• 覆盖的是需要记录结束区间的、无重叠区间需要记录结束区间

易错点：

• 摆动序列初始res=1，因为题目中规定元素少于两个也是摆动序列
• 最大子序和初始res=-Infinity
• 跳跃游戏IIfor循环的上界为length-1，因为最后一个位置是到达位置，不必计算
• k次取反后取最大值的数组和，排序需要使用绝对值进行排序
• 根据身高重建队列，对身高进行排序需要注意，按身高从大到小排序；如果身高相同则排序小的在前、
• 无重叠区间需要记录结束区间
• 无重叠区间与合并区间的差异
• 监控二叉树不熟练