贪心算法的核心思想是每次取当前最优解达到全局最优解，通常使用反证法来证明，但是要注意有的问题每次取局部最优不一定为全局最优。
6.1 分饼干
问题描述：要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
输入: g = [1,2,3], s = [1,1]
输出: 1
思路：对于每个孩子应该给它最少能满足的饼干，而且为了满足更多的孩子，应该从胃口最小的孩子开始发。
示例代码：
func findContentChildren(g []int, s []int) int {
sort.Ints(g)
sort.Ints(s)
ans, j := 0, 0
for _, vg := range g {
for ; j < len(s); j++ {
if s[j] >= vg {
ans++
j++
break
}
}
if j >= len(s) {
break
}
}
return ans
}
6.2 无重叠区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
思路：先找到最多能组成的不重合区间数量，然后总数减去该值即所求结果。对于每个区间，主要关注右端，右端最小的区间就是首个区间。（详细解释可参见LeetCode官方题解）
示例代码：
func eraseOverlapIntervals(intervals [][]int) int {
if len(intervals) < 2 {
return 0
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][1] < intervals[j][1]
})
cnt, end := 1, intervals[0][1]
for i := 1; i < len(intervals); i++ {
if intervals[i][0] >= end {
cnt++
end = intervals[i][1]
}
}
return len(intervals) - cnt
}
6.3 非递减数列
问题描述：给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
思路：尝试逐步将数列改为非递减数列，如果需要修改元素的次数大于1则不满足。当nums[i] > nums[i+1]时需要修改一个元素将其变为非递减，此时优先将nums[i]=nums[i+1]，因为改小nums[i]不会影响之前的结果。如果改大nums[i+1]可能导致nums[i+1] > nums[i+1] (原本是小于等于)。但是当nums[i-1] > nums[i+1]时只能将nums[i+1]=nums[i]，否则会导致nums[i-1] > nums[i]。
示例代码：
func checkPossibility(nums []int) bool {
cnt := 0
for i := 0; i < len(nums) - 1 && cnt < 2; i++ {
if nums[i] <= nums[i+1] {
continue
}
cnt++
if i >= 1 && nums[i-1] > nums[i+1] {
nums[i + 1] = nums[i]
} else {
nums[i] = nums[i + 1]
}
}
return cnt <= 1
}
