概念

贪心算法其实可以认为是问题的一个特例，除了动态规划的各种特征外，贪心算法还需要满足“贪心选择性质”，当然效率也比动态规划要高。

贪心选择性质：每一步走做出一个局部最优的选择，最终的结果就是全局最优。

当然，并不是所有问题都是这样的，很多问题局部最优并不难保证全局最优，只有小部分问题具有这种特质。
比如，你前面堆满了金条，你只能拿5根，怎么保证拿到的价值最大？答案当然是：每次都拿剩下的金条中最重的那根，那么最后你拿到的一定是最有价值的。
比如，斗地主，对方出了一个3，你手头有345678还有一个2，按照贪心选择，这时候你应该出4了，实际上咱们会尝试出2，然后345678芜湖起飞～🛫️

image.png

背包问题

问题1

image.png

image.png

image.png

问题2

image.png

问题3

image.png

image.png

image.png

image.png

image.png

Interval Scheduling区间调度问题

有许多[start，end]的闭区间，请设计一个算法，算出这些区间中，最多有几个互不相交的区间。

这个问题在现实中其实有很多应用场景，比如你今天有好几个活动可以参加，每个活动区间用[start, end]表示开始和结束时间，请问你今天最多能参加几个活动？

贪心求解

  1. 可以每次选择可选区间中 开始最早 的那个？
    1. 不行，因为可能有区间开始很早，结束却很晚，比如[0, 10]，使我们错过了很多短区间比如[1, 2], [2, 3]

  2. 可以每次选择可选区间中 最短 的那个？

    1. 不行，直接看上面这个例子[1, 3], [2, 4], [3, 6]，这样的话会选择出 [1, 3], [2, 4]，并不能保证他们不相交。

  3. 正确思路：

在选择要保留的区间时，区间的结尾非常重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。
因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。

    1. 从可选区间intvs里，选择一个end最小的区间x
    1. 把所有与x相交的区间从intvs中剔除（start < xEnd）
    1. 重复1，2直到intvs为空，之前选出的各种区间x，就是我们要求的结果

步骤1可以按每个区间的 end 数值升序排序。所以与 x 相交的区间必然会与 x 的 end 相交；如果一个区间不想与 x 的 end 相交，它的 start 必须要大于（或等于）x 的 end。

把整个思路转换成代码的话，因为我们要选出end最小的区间，所以我们可以先对区间根据end升序排序

  1. 选出end最小的区间
    1. 由于我们已经排过序了，所以直接选择第一个区间即可
  2. 剔除与x相交的区间
    1. 这一步就没第一步那么简单了，这里建议大家画个图看看

image.png

LC.435无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。 注意： 1.可以认为区间的终点总是大于它的起点

  1. 区间 [1, 2]和[2 ,3] 的边界相互“接触”，但没有相互重叠

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

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

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

  • 贪心算法

之前我们已经学会找出最多有几个互不相交的区间数n，那么总数减去n就可以了～

  • 记录保留（不重叠）的区间个数

问题转换成求最多有几个区间不会重叠，剩下的就是至少需要去除的区间

  1. var eraseOverlapIntervals = function (intervals) {
  2.     if (intervals.length === 0) {
  3.         return 0
  4.     }
  5.     intervals.sort((a, b) => a[1] - b[1]); // 根据End升序排序
  7.     let retainCount = 1; // 记录保留的区间（不重叠区间数量），至少有一个区间不相交
  9.     let xEnd = intervals[0][1]; // 排序后，第一个区间就是最小的xEnd
  11.     for (const [start, end] of intervals) {
  12.         // 注意，这里题目说了区间 [1, 2]和[2, 3] 的边界相互“接触”，但没有相互重叠，所以应该是item[0] >= xEnd
  13.         if (start >= xEnd) {
  14.             xEnd = end;
  15.             retainCount++;
  16.         }
  17.     }
  18.       // 总共区间数量 - 最多不重叠区间数量 即为需要剔除的最小区间数量
  19.     return intervals.length - retainCount;
  20. }
  22. console.log(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]]))
  23. console.log(eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]]))
  24. console.log(eraseOverlapIntervals([[1, 2], [2, 3]]))
  • 记录重叠的区间个数 (两次方法排序不同)
var eraseOverlapIntervals = function (intervals) {
    if (intervals.length === 0) return 0;

    intervals.sort((a, b) => a[1] - b[1]); // 根据End生序排序

    let xEnd = intervals[0][1]; // 排序后，第一个区间就是最小的xEnd

    let count = 0; // 记录重叠区间

      // 剔除与x重叠的区间，记录重叠数量count
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < xEnd) { // 重叠了，count+1
            count++;
        } else { // 没重叠，更新xEnd
            xEnd = intervals[i][1];
        }
    }
    return count;
};

var eraseOverlapIntervals = function (intervals) {
    if (intervals.length === 0)
        return 0;
    intervals.sort((a, b) => a[0] - b[0]);

    let count = 0;
    let xEnd = intervals[0][1];

      // 剔除与x重叠的区间，记录重叠数量count
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < xEnd) {
            // 重叠了，移除一个count+1，更新尾部位置取小的；
            count++;
            xEnd = Math.min(xEnd, intervals[i][1]);
        } else {
            // 没重叠，更新尾部位置
            xEnd = intervals[i][1];
        }
    }
    return count;
}

问题2:用最少的箭头射爆气球

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。

一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一直箭，若有一个气球的直径的开始和结束坐标为xstart，xend，且满足 xstart <= x <= xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

输入：10, 16], [2, 8], [1, 6], [7, 12
输出：2
解释：对于该样例，我们可以在x = 6（射爆 [2, 8],[1, 6] 两个气球）和 x = 11 （射爆另外两个气球）。

解答：
这个问题和区间调度算法又是非常的类似。
如果最多有n个不重叠的空间，那么就至少需要n个箭头穿透所有空间，所以我们要求的其实就是最多有几个不重叠的空间。
一张图？？？？
但是这个题里的描述，边界重叠后，箭头是可以一起射爆的，所以两个区间的边界重叠也算是区间重叠。
image.png

image.png

image.png

image.png

image.png

分配问题

有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃最多一个饼干，且只有饼干的大小大于等于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

输入：[1, 2] [1, 2, 3]
输出：2
解释：1吃1，2吃2，孩子1、2都吃饱了。2个孩子

解答：
因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个饥饿度最小度孩子（最饿的孩子：WDNMD）。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度度、且大小最小度饼干给这个孩子。满足了这个孩子之后，我们采取同样度策略，考虑剩下孩子里饥饿度最小度孩子，直到没有满足条件度饼干存在。
简而言之，这里的贪心策略是，给剩余孩子里饥饿度最小的孩子分配最小的能饱腹的饼干。至于具体实现，因为我们需要获得小大关系，一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对子可以满足条件。
image.png

哈夫曼编码

image.png

image.png

image.png

image.png

贪心算法的应用

image.png

image.png

image.png

买卖股票的最佳时机II - leetcode122

image.png

贪心策略：如果今天买明天卖可以赚钱，那就买入。

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 0 ;i<prices.length -1 ;i++){
            if(prices[i]<prices[i+1])
            profit+=prices[i+1]-prices[i];
        }
        return profit;
    }
}