贪心算法

发表于 2022-04-18 分类于算法思想本文字数： 8.7k 阅读时长 ≈ 8 分钟

贪心算法

应用场景：解决一个问题需要多个步骤，每一步骤有多种选择。使用贪心算法，每一步只需要解决一个子问题，只做出一种选择，就可以完成任务。

关于贪心算法与回溯算法、动态规划的区别

「回溯算法」需要记录每一个步骤、每一个选择，用于回答所有具体解的问题；
「动态规划」需要记录的是每一个步骤、所有选择的汇总值（最大、最小或者计数）；
「贪心算法」由于适用的问题，每一个步骤只有一种选择，一般而言只需要记录与当前步骤相关的变量的值。

使用「贪心算法」的问题需要满足的条件

最优子结构：规模较大的问题的解由规模较小的子问题的解组成，区别于「动态规划」，可以使用「贪心算法」的问题「规模较大的问题的解」只由其中一个「规模较小的子问题的解」决定；
无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果；
贪心的实质：从局部最优到全局最优。

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

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

思路：
为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。

使用贪心的话：首先对数组 g 和 s 排序，然后从小到大遍历 g 中的每个元素，对于每个元素找到能满足该元素的 s 中的最小的元素。具体而言，令 i 是 g 的下标，j 是 s 的下标，初始时 i 和 j 都为 0，进行如下操作。

class Solution{
	public int findContentChildren(int[] g,int[] s){
		Arrays.sort(g);
		Arrays.sort(s);
		int len1 = g.length , len2 = s.length;
		int count = 0;
		for(int i=0,j=0; i<len1 && j<len2 ;i++,j++){
			while(j<len2 && g[i]>s[j]){
				j++;
			}
			if(j<len2){
				count++;
			}
		}
		return count;
	}
}

典型题型分析：

找零钱问题

具体：在生活中，我们找给别人零钱，通常都是按照「先给出尽可能多的面值较大的纸币（硬币），然后再给出尽可能多的面值第二大的纸币（硬币）」，直到凑成了我们需要凑出的金额为止，这样找零钱得到的纸币（硬币）的张数（个数）最少。能够这样做，与可选的硬币（纸币）的面值密切相关。

例题：

描述: 在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

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

解题思路：
由于顾客只可能给你三个面值的钞票，而且我们一开始没有任何钞票，因此我们拥有的钞票面值只可能是 5 美元，10 美元和 20 美元三种。基于此，我们可以进行如下的分类讨论。

5 美元，由于柠檬水的价格也为 5 美元，因此我们直接收下即可。
10 美元，我们需要找回 5 美元，如果没有 5 美元面值的钞票，则无法正确找零。
20 美元，我们需要找回 15 美元，此时有两种组合方式，一种是一张 10 美元和 5 美元的钞票，一种是 3 张 5 美元的钞票，如果两种组合方式都没有，则无法正确找零。当可以正确找零时，两种找零的方式中我们更倾向于第一种，即如果存在 5 美元和 10 美元，我们就按第一种方式找零，否则按第二种方式找零。

代码如下：

class Solution{
	public boolean lemonChange(int[] bills){
		int five = 0, ten = 0;
		for(int bill: bills){
			if(bill == 5){
				five++;
			}else if(bill == 10){
				if(five == 0){
					return false;
				}
				five--;
				ten++;
			}else {
				if(five>0 && ten>0){
					five--;
					ten--;
				}else if(five >= 3){
					five-=3;
				}else{
					return false;
				}
			}
		}
		return true;
	}
}

总结：这道题的贪心思想，完全是因为可以选择的钞票面值只有 5 美元，10 美元和 20 美元。

区域选择问题

无重叠区间：

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

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

解法一：动态规划
由于选出的区间互不重叠，因此我们可以将它们按照端点从小到大的顺序进行排序，并且无论我们按照左端点还是右端点进行排序，得到的结果都是唯一的。这样一来，我们可以先将所有的 n 个区间按照左端点（或者右端点）从小到大进行排序，随后使用动态规划的方法求出区间数量的最大值。设排完序后这 n 个区间的左右端点分别为 l_i 和 r_i,然后可以令 f_i 表示「以区间 i 为最后一个区间，可以选出的区间数量的最大值」。

代码如下：

class Solution{
	public int eraseIntervals(int[][] intervals){
		if(intervals.length == 0){
			return 0;
		}

		Arrays.sort(intervals,new Comparator<int[]>(){
			public int compare(int[] interval1,int[] interval2){
				return interval1[0] - interval2[0];
			}
		});
		int n = intervals.length;
		int[] f = new int[n];
		Arrays.fill(f,1);
		for(int i=1; i<n;i++){
			for(int j=0;j<i;j++){
				if(intervals[j][1]<=intervals[i][0]){
					f[i]=Math.max(f[i],f[j]+1);
				}
			}
		}
		return n - Arrays.stream(f).max().getAsInt();
	}
}

解法二：贪心
可以不断地寻找右端点在首个区间右端点左侧的新区间，将首个区间替换成该区间。那么当我们无法替换时，首个区间就是所有可以选择的区间中右端点最小的那个区间。因此我们将所有区间按照右端点从小到大进行排序，那么排完序之后的首个区间，就是我们选择的首个区间。

当确定了首个区间之后，所有与首个区间不重合的区间就组成了一个规模更小的子问题。由于我们已经在初始时将所有区间按照右端点排好序了，因此对于这个子问题，我们无需再次进行排序，只要找出其中与首个区间不重合并且右端点最小的区间即可。用相同的方法，我们可以依次确定后续的所有区间。

代码如下：

class Solution{
	public int eraseIntervals(int[][] intervals){
		if(intervals.length==0){
			return 0;
		}
		Arrays.sort(intervals,new Comparator<int[]>(){
			public int compare(int[] inter1,int[] inter2){
				return inter1[1]-inter2[1];
			}
		});
		int n = intervals.length;
		int r = intervals[0][1];
		int ans = 1;
		for(int i=1; i<n;i++){
			if(intervals[i][0]>=r ){
				++ ;
				r = intervals[i][1];
			}
		}
		return n - ans ;
	}
}

用最少数量的箭引爆气球

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

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

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

示例：
输入:
[[10,16], [2,8], [1,6], [7,12]]

输出:
2

解释:
对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。

分析：
存在一种最优（射出的箭数最小）的方法，使得每一支箭的射出位置都恰好对应着某一个气球的右边界。
对于其中的任意一支箭，我们都通过上面描述的方法，将这支箭的位置移动到它对应的「原本引爆的气球中最靠左的右边界位置」，那么这些原本引爆的气球仍然被引爆。这样一来，所有的气球仍然都会被引爆，并且每一支箭的射出位置都恰好位于某一个气球的右边界了。
有了这样一个有用的断定，我们就可以快速得到一种最优的方法了。考虑所有气球中右边界位置最靠左的那一个，那么一定有一支箭的射出位置就是它的右边界（否则就没有箭可以将其引爆了）。当我们确定了一支箭之后，我们就可以将这支箭引爆的所有气球移除，并从剩下未被引爆的气球中，再选择右边界位置最靠左的那一个，确定下一支箭，直到所有的气球都被引爆。

伪代码：

let points := [[x(0), y(0)], [x(1), y(1)], ... [x(n-1), y(n-1)]]，表示 n 个气球
let burst := [false] * n，表示每个气球是否被引爆
let ans := 0，表示射出的箭数

将 points 按照 y 值（右边界）进行升序排序

while burst 中还有 false 值 do
    let i := 最小的满足 burst[i] = false 的索引 i
    for j := i to n-1 do
        if x(j) <= y(i) then
            burst[j] := true
        end if
    end for
end while

return ans

完整代码如下：

class Solution{
	public int findMinArrows(int[][] points){
		if(points.length==0){
			return 0;
		}
		Arrays.sort(points,new Comparator<int[]>()}{
			public int compare(int[] point1,int[] point2){
				if(point1[1]>point2[1]){
					return 1;
				}else if(point1[1]<point2[1]){
					return -1;
				}else{
					return 0;
				}
			}
		});
		int pos = points[0][1];
		int ans = 1;
		for(int[] balloon:points){
			if(balloon[0]>pos){
				pos = balloon[0];
				++ans;
			}
		}
		return ans;
	}
}

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

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

思路：
首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：

如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

代码如下：

class Solution{
	public int[][] merge(int[][] intervals){
		if(intervals.length == 0){
			return new int[0][2];
		}
		Arrays.sort(intervals,new Comparator<int[]>(){
			public int compare(int[] inter1 , int[] inter2){
				return inter1[0] - inter2[0];
			}
		});
		List<int[]> merged = new ArrayList<>();
		for(int i=0 ; i<intervals.length ; i++){
			int l = intervals[i][0] , r= intervals[i][1];
			if(merged.size() == 0 || merged.get(merge.size()-1)[1]< l){
				merged.add(new int[]{l,r}) ;
			}else{
				merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1] ,r);
			}
		}
		return merged.toArray(new int[merged.size()][]);
	}
}

跳跃游戏

描述：

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

示例1：
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

思路：
对于数组中的任意一个位置 y , 我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x + nums[x]，这个值大于等于 y ,那么位置 y 就可达到。
换句话说，对于每一个可以到达的位置 x，它使得 x+1, x+2, ⋯,x+nums[x] 这些连续的位置都可以到达。
这样一来，我们依次遍历数组中的每一个位置，并且实时维护 最远可达位置 ，对于当前遍历到的位置 x ，如果他在最远可以达到的位置的范围内，我们就可以从起点通过若干次跳跃到达该位置，可以用 x+nums[x] 更新 最远可以到达的位置。

代码如下：

public class Solution{
	public boolean canJump(int[] nums){
		int n = nums.length;
		int rightmost = 0;
		for(int i=0;i<n;i++){
			if(i<=rightmost){
				rightmost = Math.max(rightmost,i+nums[i]);
				if(rightmost >= n-1){
					return true;
				}
			}
		}
		return false;
	}
}

跳跃进阶

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

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

方法一：反向查找出发位置
我们的目标是到达数组的最后一个位置，因此我们可以考虑最后一步跳跃前所在的位置，该位置通过跳跃能够到达最后一个位置。
如果有多个位置通过跳跃都能够到达最后一个位置，那么我们应该如何进行选择呢？直观上来看，我们可以「贪心」地选择距离最后一个位置最远的那个位置，也就是对应下标最小的那个位置。因此，我们可以从左到右遍历数组，选择第一个满足要求的位置。
找到最后一步跳跃前所在的位置之后，我们继续贪心地寻找倒数第二步跳跃前所在的位置，以此类推，直到找到数组的开始位置。

代码如下：

public class Solution{
	public int canJump(int[] nums){
		int pos = num.length - 1;
		int steps = 0;
		while(pos > 0){
			for(int i=0; i<pos; i++){
				if(i+nums[i] > =pos){
					pos = i;
					steps++;
					break;
				}
			}
		}
		return steps;
	}
}

方法二：正向查找可达到的最大位置
如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。
例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。
从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。
具体实现：
我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。
在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。

代码如下：

public class Solution{
	public int canJump(int[] nums){
		int len = nums.length;
		int end = 0;
		int maxPos = 0;
		int steps = 0;
		for(int i=0 ;i<len-1 ;i++){
			maxPos = Math.max(maxPos,i+nums[i]);
			if(i == end){
				end = maxPos;
				steps++;
			}
		}
		return steps ;
	}
}