Leetcode-100 贪心算法

贪心算法简介

贪心算法（Greedy Algorithm）是一种常见的优化算法，用于解决最优化问题。该算法的核心思想是每次选择当前情况下的最优解，并期望通过这些局部最优解得到全局最优解。贪心算法通常用于那些可以分解为若干个子问题，且每个子问题的最优解可以合成全局最优解的问题。

贪心算法之所以有用，是因为它可以快速地做出决策，并能在某些问题上实现较高的效率，避免了回溯与暴力解法的复杂度。

贪心算法思想

贪心算法的基本思想是：每次选择最优的局部解，期待通过这些局部解达到全局最优。每一步做出决策时，贪心算法并不考虑未来的选择。它的核心假设是：通过局部最优的选择，最终能得到全局最优的解。

在实际应用中，贪心算法往往具有以下特点：

• 局部最优选择：每次选择当前问题的最优解，期望通过这些局部最优的选择获得全局最优解。
• 无回溯：每做一次选择后，算法不会再回到之前的状态，而是继续推进。

贪心算法的基本特征

1. 局部最优性：
   贪心算法在每个阶段做出局部最优选择，即在当前状态下，选择最有利的行动。假设这些局部最优选择可以合成全局最优解。

2. 无回溯性：
   贪心算法一旦做出决策，就不再回溯，直接向下一个阶段推进。这种策略可以大大减少计算量。

3. 问题分解：
   贪心算法适用于那些可以将问题分解为一系列子问题的情况，并且通过解决这些子问题来得到最优解。

贪心算法的应用条件

贪心算法适用于以下两类问题：

1. 贪心选择性质：

   • 问题的最优解包含了它的子问题的最优解。即当前的局部最优解能够推动全局最优解的产生。

2. 最优子结构：

   • 问题的解可以由子问题的解构成，子问题的解必须是最优的，并且不依赖于其他的解决方式。

这两个条件保证了贪心算法能够通过局部最优选择来得到全局最优解。

贪心算法的步骤

要使用贪心算法来解决问题，可以按照以下步骤进行：

1. 定义子问题：
   将问题分解为若干个子问题，且这些子问题的最优解能构成问题的最优解。

2. 选择最优策略：
   设计一个贪心策略，每次选择当前最优的子问题解。

3. 构建解：
   根据贪心策略，通过逐步构建解来求得最优解。

4. 验证最优性：
   证明每个局部最优选择能导致全局最优解。

贪心算法题例

接下来我们通过两个经典的题目来深入理解贪心算法：跳跃游戏I 和 跳跃游戏II。

6.1 跳跃游戏I（Jump Game I）

问题描述：

给定一个数组 nums，数组中的每个元素表示从当前位置能够跳跃的最大步数。你从 nums[0] 开始，返回是否能到达最后一个位置。

贪心策略：

从左到右遍历数组，维护一个变量 farthest 表示当前能到达的最远位置。如果在某一时刻，farthest 达到了或超过了最后一个位置，说明我们能够到达最后的位置。

贪心策略说明：

• 每一位置的跳跃范围可以由当前的最大可跳跃步数决定。
• 如果当前位置 i 不能达到 farthest，说明无法到达最后一个位置，直接返回 False。

代码实现：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0  # 当前能跳到的最远位置
        for i in range(len(nums)):
            if i > farthest:  # 如果当前位置超过了最远可跳的位置，返回 False
                return False
            farthest = max(farthest, i + nums[i])  # 更新最远可跳的位置
        return True  # 如果能遍历所有位置，返回 True

时间复杂度：

• O(n)，我们只需要遍历一次数组。

空间复杂度：

• O(1)，只使用了常数空间。

6.2 跳跃游戏II（Jump Game II）

问题描述：

给定一个非负整数数组 nums，其中每个元素表示从该位置能够跳跃的最大步数。要求你返回到达最后一个位置所需的最小跳跃次数。

贪心策略：

• 维护一个 end 变量表示当前跳跃范围的结束位置。
• 维护一个 farthest 变量表示当前跳跃范围内可以到达的最远位置。
• 每当遍历到 end 位置时，更新跳跃次数，并将 end 更新为 farthest。

贪心策略说明：

• 在每次更新 end 时，跳跃次数增加 1。
• 遇到 end 时，说明当前跳跃已经结束，需要选择一个新的跳跃范围。

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        farthest = 0
        end = 0
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])  # 更新能到达的最远位置
            if i == end:  # 当到达当前跳跃的最远位置时，增加跳跃次数
                jumps += 1
                end = farthest  # 更新跳跃的结束位置
        return jumps

时间复杂度：

• O(n)，我们只需要遍历一次数组。

空间复杂度：

• O(1)，只使用了常数空间。

总结