一、算法概念
- 贪心算法是一种基于贪心策略的算法设计方法。
二、基本思想
- 在解决问题时，贪心算法每一步都选择当前最优的解决方案，而不考虑后续步骤可能产生的影响。具体来说，贪心算法会选择当前情况下的
局部最优解，并希望通过不断地做出局部最优选择，最终达到全局最优解。
三、算法步骤
贪心算法的步骤如下：
-
确定问题的
最优子结构：将原始问题划分为多个子问题，每个子问题都应该有一个最优解。 -
构建
贪心选择性质：通过贪心选择性质，每一步都选择当前最优解，希望通过不断地做出局部最优选择，最终得到全局最优解。 -
定义
贪心策略：确定问题的优化目标，并根据问题的特点制定相应的贪心策略。这个策略可以基于某种指标、规则或者其他方法。 -
递归地或者循环地解决子问题：通过贪心策略，递归地或者循环地解决每个子问题。这个过程中，每一步都会选择当前最优解。 -
检查解是否满足问题的
约束条件：在得到解之后，需要检查解是否满足问题的约束条件。如果满足约束条件，则认为找到了最优解；否则，需要进行进一步的调整。
需要注意的是，贪心算法的关键在于选择当前的最优解。这个选择可以基于某种指标、规则或策略，根据问题的具体特性来确定。
四、简单实现示例
题目：盛最多水的容器
给定一个长度为 n 的整数数组 height 。
有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例：
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组[1,8,6,2,5,4,8,3,7]。
在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：输入：height = [1,1]
输出：1
提示：
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
解法：
按照贪心算法解决步骤如下：
-
确定问题的最优子结构：考虑容器能够容纳最多的水，我们可以将容器的面积定义为两条线段的长度乘以它们之间的距离，即
面积 = (j - i) * min(height[i], height[j])，其中 i 和 j 分别为两条线段的索引。我们要找到最大的面积，也就是要找到最大的 (j - i) * min(height[i], height[j])。 -
构建贪心选择性质：在每一步中，我们
选择两条线段中较短的一条向内移动，希望通过不断地选择较短的线段，找到更高的线段来计算面积。 -
定义贪心策略：我们可以使用双指针的方法来解决该问题。我们将左指针指向数组的起始位置，右指针指向数组的末尾位置。计算当前的面积，并记录下最大的面积。然后，我们比较两条线段的高度，将高度较小的那条线段的指针向内移动一位。重复以上步骤，直到两个指针相遇。
-
递归地或者循环地解决子问题：通过贪心策略，不断地移动指针，计算每个位置的面积，找到最大的面积。
-
检查解是否满足问题的约束条件：在得到最大面积之后，满足问题约束条件，即两个指针相遇。
下面是使用Java语言实现的代码：
public int maxArea(int[] height) {int maxArea = 0;int left = 0;int right = height.length - 1;while (left < right) {int area = (right - left) * Math.min(height[left], height[right]);maxArea = Math.max(maxArea, area);if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;
}
在代码中，我们使用双指针的方法，通过移动指针来计算每个位置的面积，并记录下最大的面积。最终返回最大面积即可。
五、10种应用场景及对应的步骤拆解
-
最小生成树问题：步骤拆解如下：
- 定义问题的最优子结构：找到一棵包含所有顶点的生成树，使得生成树的边权重之和最小。
- 构建贪心选择性质：在每一步中，选择权重最小的边添加到生成树中，且不能形成环。
- 定义贪心策略：使用Prim算法或Kruskal算法来构建最小生成树。
- 递归地或循环地解决子问题：通过贪心策略，不断地选择边，构建生成树。
- 检查解是否满足问题的约束条件：生成树包含所有顶点且边权重之和最小。
-
活动选择问题：步骤拆解如下：
- 定义问题的最优子结构：找到最大化能够安排的活动数量的子集，且每个活动的结束时间不重叠。
- 构建贪心选择性质：在每一步中，选择结束时间最早的活动添加到子集中。
- 定义贪心策略：对活动按照结束时间进行排序，选择结束时间最早的活动。
- 递归地或循环地解决子问题：通过贪心策略，不断地选择活动，构建最大化能够安排的活动数量的子集。
- 检查解是否满足问题的约束条件：每个活动的结束时间不重叠。
-
零钱兑换问题：步骤拆解如下：
- 定义问题的最优子结构：找到使用最少数量的硬币组成给定的金额。
- 构建贪心选择性质：在每一步中，选择面值最高且能够组成金额的硬币。
- 定义贪心策略：对硬币按照面值进行排序，选择面值最高且能够组成金额的硬币。
- 递归地或循环地解决子问题：通过贪心策略，不断选择硬币，组成金额。
- 检查解是否满足问题的约束条件：使用最少数量的硬币组成给定的金额。
-
哈夫曼编码问题：步骤拆解如下：
- 定义问题的最优子结构：找到一种编码方式，使得编码后的字符串长度最小。
- 构建贪心选择性质：在每一步中，选择权重最小的字符对进行编码。
- 定义贪心策略：使用哈夫曼树构建编码方式，其中权重较小的字符位于树的较低层。
- 递归地或循环地解决子问题：通过贪心策略，不断地选择字符对，构建哈夫曼树。
- 检查解是否满足问题的约束条件：编码后的字符串长度最小。
-
频率分配问题：步骤拆解如下：
- 定义问题的最优子结构：给定一组频率，将其分配到一组资源上，使得总分配代价最小。
- 构建贪心选择性质：在每一步中，选择频率最大的资源进行分配。
- 定义贪心策略：对频率进行排序，选择频率最大的资源进行分配。
- 递归地或循环地解决子问题：通过贪心策略，不断地选择资源，进行频率分配。
- 检查解是否满足问题的约束条件：总分配代价最小。
-
区间覆盖问题：步骤拆解如下：
- 定义问题的最优子结构：找到最小数量的区间，使得它们覆盖给定的集合。
- 构建贪心选择性质：在每一步中，选择右端点最早的区间进行覆盖。
- 定义贪心策略：对区间按照右端点进行排序，选择右端点最早的区间进行覆盖。
- 递归地或循环地解决子问题：通过贪心策略，不断地选择区间进行覆盖。
- 检查解是否满足问题的约束条件：覆盖给定的集合。
-
跳跃游戏问题：步骤拆解如下：
- 定义问题的最优子结构：找到最少的跳跃次数，从数组的起始位置跳到最后一个位置。
- 构建贪心选择性质：在每一步中，选择能够跳得最远的位置进行跳跃。
- 定义贪心策略：选择当前能够跳得最远的位置进行跳跃。
- 递归地或循环地解决子问题：通过贪心策略，不断地选择位置进行跳跃，直到到达最后一个位置。
- 检查解是否满足问题的约束条件：跳到最后一个位置，并且跳跃次数最少。
-
区间调度问题：步骤拆解如下：
- 定义问题的最优子结构：找到最多的不重叠区间子集。
- 构建贪心选择性质：在每一步中，选择结束时间最早的区间。
- 定义贪心策略：对区间按照结束时间进行排序，选择结束时间最早的区间。
- 递归地或循环地解决子问题：通过贪心策略，不断地选择区间，构建最多的不重叠区间子集。
- 检查解是否满足问题的约束条件：最多的不重叠区间子集。
-
分割回文串问题：步骤拆解如下：
- 定义问题的最优子结构：找到最少的分割次数，将字符串分割为一些回文串子串。
- 构建贪心选择性质：在每一步中，选择最长的回文串子串进行分割。
- 定义贪心策略：选择当前最长的回文串子串进行分割。
- 递归地或循环地解决子问题：通过贪心策略，不断地选择回文串子串进行分割，直到将整个字符串分割为回文串子串。
- 检查解是否满足问题的约束条件：最少的分割次数。
-
图的着色问题：步骤拆解如下：
- 定义问题的最优子结构：找到使用最少数量的颜色为无向图中的每个顶点着色，使得相邻的顶点颜色不同。
- 构建贪心选择性质：在每一步中，选择最小的可用颜色对当前顶点进行着色。
- 定义贪心策略：选择最小的可用颜色对当前顶点进行着色。
- 递归地或
六、算法优缺点
优点：
- 简单易实现：贪心算法通常只需要对问题进行一次遍历，每次选择当前最优解即可，代码实现相对简单。
- 效率高：由于贪心算法每次选择当前最优解，可以减少计算量，从而提高算法的运行效率。
- 可以解决一些特殊类型的问题：贪心算法适用于一些满足贪心选择性质的问题，如活动选择问题、最小生成树问题等。
缺点：
- 得不到全局最优解：由于贪心算法每次只选择当前最优解，并没有考虑到后续步骤的影响，所以不能保证能够得到全局最优解。
- 需要证明贪心选择性质：在应用贪心算法时，需要证明问题具有贪心选择性质，即每一步选择都是最优选择，这对于一些问题来说可能是困难的。
在应用贪心算法时，需要注意问题的特性，确保贪心选择性质成立，并验证算法的正确性。
七、常见面试题及解法
-
区间调度问题：
- 题目描述：给定一组区间，选择最多的不重叠区间。
- 步骤解法：按照结束时间对区间进行排序，然后依次选择结束时间最早的区间，并且保证不与已选区间重叠。
-
分配饼干问题：
- 题目描述：给定一组孩子和一组饼干的大小，每个孩子只能分配一块饼干，求最多能满足的孩子数量。
- 步骤解法：对孩子和饼干的大小进行排序，然后依次匹配最小的饼干给胃口最小的孩子，直到没有更多的饼干或孩子。
-
跳跃游戏问题：
- 题目描述：给定一个非负整数数组，初始位置在数组的第一个位置，每个元素代表你在该位置可以跳跃的最大长度，判断能否到达最后一个位置。
- 步骤解法：从起始位置开始，遍历数组，记录当前能够到达的最远位置，如果最远位置超过数组长度，则可以到达最后一个位置。
-
零钱兑换问题：
- 题目描述：给定一组不同面额的硬币和一个总金额，计算可以凑成总金额所需的最少硬币数量。
- 步骤解法：从总金额开始，依次选择面额最大的硬币，并且减去当前选择的硬币金额，直到金额为0。
-
买卖股票的最佳时机问题：
- 题目描述：给定一个数组，其中的第 i 个元素代表第 i 天的股票价格，计算出最大利润。
- 步骤解法：从第二天开始遍历数组，计算当天与前一天的差值，如果差值为正，则加入最大利润，否则继续遍历。
-
加油站问题：
- 题目描述：给定一个环形路线上的加油站和每个加油站的油量，以及从每个加油站到下一个加油站的距离，计算出能够绕行一圈的起始加油站的下标。
- 步骤解法：从0号加油站开始遍历，如果当前加油站的剩余油量小于0，表示无法到达下一个加油站，将当前加油站设为起始加油站，并将剩余油量清零。
-
划分字母区间问题：
- 题目描述：给定一个只包含小写字母的字符串，划分出尽可能多的区间，使得每个字母最多出现在一个区间中。
- 步骤解法：遍历字符串，记录每个字母最后出现的位置，然后根据最后出现位置进行划分，保证每个区间中的字母不会出现在其他区间。
-
最大子序和问题：
- 题目描述：给定一个整数数组，找到一个具有最大和的连续子数组，返回其最大和。
- 步骤解法：遍历数组，计算以当前元素为结尾的子数组的和，如果和小于0，则舍弃之前的子数组，重新开始计算。
-
跳跃游戏 II 问题：
- 题目描述：给定一个非负整数数组，初始位置在数组的第一个位置，每个元素代表你在该位置可以跳跃的最大长度，计算出到达最后一个位置所需的最少步数。
- 步骤解法：维护当前能够达到的最远位置，遍历数组，如果当前位置超过最远位置，则更新最远位置，并增加步数。
-
种花问题：
- 题目描述：给定一个由0和1组成的数组，其中0表示可以种花的地方，1表示已经种了花的地方，判断是否能够在数组中种下 n 朵花，且相邻的花不能相邻。
- 步骤解法：遍历数组，统计连续的0的个数，如果连续的0的个数大于等于3，则可以在该位置种花，并将花的数量减少1。
