算法解释

顾名思义，贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最 后得到的结果是全局最优的。 举一个最简单的例子：小明和小王喜欢吃苹果，小明可以吃五个，小王可以吃三个。已知苹 果园里有吃不完的苹果，求小明和小王一共最多吃多少个苹果。在这个例子中，我们可以选用的 贪心策略为，每个人吃自己能吃的最多数量的苹果，这在每个人身上都是局部最优的。又因为全 局结果是局部结果的简单求和，且局部结果互不相干，因此局部最优的策略也同样是全局最优的 策略。

分配问题

分发饼干

455. 分发饼干 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可 以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这 个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到 没有满足条件的饼干存在。

我们可以通过排序来简单的进行匹配

// 解题思路：就是我们要优先用最小的饼干来满足最小的要求
// 所以我们可以通过排序，让最小的孩子和最小的饼干进行测试，然后我们优先满足最小需求的孩子
func findContentChildren(g []int, s []int) int {
	// 首先我们给g和s进行排序
	sort.Ints(g)
	sort.Ints(s)
	// 分别用i，j来表示孩子和饼干
	i,j:=0,0
	// 当任意一个不满足时，我们就可以退出了
	for i<len(g) && j <len(s) {
		// 判断当前饼干是否满足当前孩子，如果满足孩子+1
		if g[i] <= s[j] {
			i ++
		}
		// 无论是否满足，饼干都要后移
		j++
	}
	return i
}

分发糖果

首先要确保每个孩子都有一个糖果，然后我们从左到右进行遍历，这里如果右边孩子的评分比左边高，那么我们就把右边孩子的糖果数更新为左边孩子的糖果数+1 然后我们从右往左遍历，如果左边孩子评分比右边高，同时还要确保左边孩子的糖果数不大于右边孩子，这时我们就更新左边孩子为右边孩子糖果数+1

这里注意一下，第一次遍历的时候,我们是右边比左边，所以我们直接使用i来表示右边，但是二次遍历的时候，我们是左边比右边，所以我们就应该是 i-1来进行比较。我一开始没有理解好这个相对关系。

func candy(ratings []int) int {
   // 初始化数组并全部赋值为1
   ans:=make([]int,len(ratings))
   for k:=range ans{
      ans[k] = 1
   }
   // 首先我们先满足评分更高的比左边的糖果更多
   for i:=1;i<len(ratings);i++{
      if ratings[i] > ratings[i-1] {
         // 如果评分更高，那么当前孩子要比左边的孩子糖果要多1
         ans[i] = ans[i-1] + 1
      }
   }
   // 然后我们满足评分更高的比右边的糖果更多，这里我们就从右边开始遍历
   for i:=len(ratings)-1;i>0;i--{
      // 如果左边孩子的评分比右边的高
      if ratings[i] < ratings[i-1]  {
         //且左边孩子当前的糖果数,不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1
         if ans[i]+1 > ans[i-1] {
            ans[i-1] = ans[i] + 1
         }
      }
   }
   a:=0
   // 计算糖果数
   for _,v:=range ans {
      a+=v
   }
   return a
}

区间问题

无重叠区间

435. 无重叠区间 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

贪心算法的思想在于，我们每次都要一个代价最小的来满足当前的需求，无论是前面分糖果还是后面这个区间，我们都要选择一个代价最小的，所以这道题的关键就是在于，我们每次在选择的时候，选择结尾最小的，这样我们就可以串联起更多的值。

这个题目有两个关键部分，一个是给数组排序，一般情况下，贪心算法都需要使用排序来确保我们每次选择的都是最小的。这里我我们排序的原则就是首先如果开头谁更小谁就在前，如果相等，那么结尾更小的也排在前面，这里可以看一下我们自定义排序需要重写的几个方法

然后就是后面的选择了，我们可以使用一个指针来指明当前我们已经排好的连续区间，选择的时候要确保待插入的值的最小区间要大于等于当前区间的最大值，如果小于的话，那么我们就看一下待插入区间的最大值是否比当前区间要小，如果小于的话我们也更换一下（因为我们我们已经排好序了，待插入区间的最小值一定会大于等于当前区间的最小值，我们可以替换，因为这样可以确保结尾是最小的）

// 这里我们为了进行简单排序，需要重写sort方法
type Intervals [][]int
// 获取长度
func (a Intervals) Len() int {
	return len(a)
}
// 交换数据
func (a Intervals) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
}
// 重写less方法，这里是比较两个下标
func (a Intervals) Less(i, j int) bool {
	// 我们这里是在进行区间比较，只要发现开头或结尾i比j小，那么就是小的，否则就是大的
	for k := 0; k < len(a[i]); k++ {
		if a[i][k] < a[j][k] {
			return true
		} else if a[i][k] == a[j][k] {
			continue
		} else {
			return false
		}
	}
	return true
}
func eraseOverlapIntervals(intervals [][]int) int {
	if len(intervals) == 0 {
		return 0
	}
	// 这里是对我们传入的参数进行区间排序
	// 这里排序完后，那些开头比较小的会排在前面
	// 然后如果开头相等，但是结尾较小的也会在前面
	sort.Sort(Intervals(intervals))
	// 这里因为我们要让整个区间连续不能重叠
	// 所以我们使用pre来表示当前已经连续了的区间最小位置
	pre, res := 0, 1
	// 然后我们就开始进行比较
	for i := 1; i < len(intervals); i++ {
		// 如果当前区间的开头比 pre区间的结尾大或者相等
		if intervals[i][0] >= intervals[pre][1] {
			// 这里表示区间不重叠，此时我们就可以让pre等于当前的区间，res表示连续的区间数
			res++
			pre = i
		// 如果当前区间的结尾比pre更小，那么我们可以把pre换成i
		// 这里说一下这一步的原因，因为我们要确保每次都选结尾最早的
		// 此时我们的数组是排好序了的，pre的开头一定会小于或者等于i的开头
		// 这个时候我们直接换成i可以减小结尾的长度
		} else if intervals[i][1] < intervals[pre][1] {
			pre = i
		}
	}
	return len(intervals) - res
}

练习

605，452,736,122,406,665