复杂难度贪心算法实战

在上一节介绍了一些初级的编程题后，对贪心算法有了初步的理解，接下来我们会用 leetcode 上 3 道中级和困难题目来帮助大家进一步掌握和应用贪心算法。

1. 跳跃游戏

这是 leetcode 上算法部分第55题，为中级编程题。题目描述如下：

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

示例 1：

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2：

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

这道题稍微有点复杂，官方给出的解法正是贪心思路：首先思考对于数组中任意一个位置 y, 如何判断它是否可达？根据题目表示，只要存在一个位置 x，它本身可达，且它跳跃的最大长度为 x + nums[x]，如果这个值大于等于 y，即 x + nums[x] >= y，即位置 y 也可达。对于每一个可以到达的位置 x，它使得 x+1, x+2, ... , x+nums[x] 这些连续的位置都可以到达。

这样以来，我们依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。

对于当前遍历到的位置 x, 如果它在最远可以到达的位置的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x + nums[x] 更新最远可以到达的位置。

在遍历的过程中，如果最远可以到达的位置大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。这便是官方给出的贪心思路，非常清晰明了。

最后根据上述思路我们给出完整的 Python 解答，这个题解来自 leetcode 题解中的一个优秀回答，和官方给出的贪心思路一致，都是维护一个从起始点出发可以达到的最远坐标。

def canJump(nums):
    # 如果数组中没有0，则一定可以到达
    if 0 not in nums: return True
    # 如果只有一个元素，也可以到达
    if len(nums) < 2: return True
    # 维护最长距离
    max_distance = 0
    for i in range(len(nums) - 1):
        # i <= max_distance 表明当前位置可以到达
        if i <= max_distance:
            # 更新最大距离
            max_distance = max(i + nums[i], max_distance)
        else:
        # 如果当前位置无法到达则结束    
            break
    # 返回能到达的最大距离是否能到最后一位
    return max_distance >= len(nums) - 1 

我们来看看官方给出的示例代码，也比较精简，思路和原理一样，只不过代码写法不同。原代码为 java，现转成 Python，内容如下：

def canJump(nums):
    # 维持最大距离
    max_distance = 0
    for i in range(len(nums)):
        # 非常重要，该点必须可达
        if i <= max_distance:
            # 该点可达，更新能到的最大距离
            max_distance = max(i + nums[i], max_distance)
            # 如归最大距离能到最后一个位置，直接返回 True
            if max_distance >= (len(nums) - 1):
                return True
        else:
            # 如果i位置无法到达，那么可以直接退出循环，返回False
            break
    # 无法到达最后，返回False
    return False 

2. 情侣牵手

这是 leetcode 上算法部分的第765题，属于困难级别，题目描述如下：

N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。

人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。

这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。

示例 1：

输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。

示例 2：

输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

Tips：

• len(row) 是偶数且数值在 [4, 60]范围内；

• 可以保证row 是序列 0...len(row)-1 的一个全排列。

这道题虽然给出困难级别，但是主要是针对使用 O(n) 的算法。如果使用简单的贪心算法，时间复杂度为 $O(n^2)$，且解题思路非常清晰。

官方给出的第三种解法正是贪心算法，其思路为：每处理一对元素，如果第二个元素不是第一个元素的情侣，那么就在全局找到第一个元素的情侣，交换他们的位置；依此操作，知道最后一对情侣被安排好。

其中对于位置编号为 x 的人，其情侣编号为 x^1 (^表示异或)，这样的写法比较精妙，难以想到，也算是一个小的技巧。有了这个思路，来直接写出相应的 Python 代码，如下：

def minSwapsCouples(row):
    if len(row) <= 2:
        return 0

    res = 0
    for i in range(0, len(row), 2):
        # row[i]的情侣编号
        couple_id = row[i] ^ 1
        # 如果旁边正好是他的情侣，直接下一对继续判断
        if row[i + 1] == couple_id:
            continue
        # 如果不是，则需要一次交换
        res += 1
        # 遍历后续的人，找到row[i]的情侣，然后交换和row[i+1]的位置
        for j in range(i + 2, len(row)):
            if row[j] == couple_id:
                row[i + 1], row[j] = row[j], row[i + 1]
                break
    # 返回总的交换次数
    return res

从上面可以看到，算法使用了两个 for 循环，时间复杂度为 O(n^2)。第二个 for 循环是找对应 row[i] 的情侣，有没有办法加快查找速度呢？在 leetcode 的题解中，有人给出了一个优化的解法：将编号和其当前所在位置的映射关系单独使用一个列表保存，这样我们查找比如编号为 i 的所在的位置时只需要 O(1) 的复杂度即可：

for j in range(len(row)):
    seatmap[row[j]] = j

之所以能这样做的原因就在于题目说明中的第二点：row 中元素的编号是序列 0...len(row)-1 的一个全排列。这是一个典型的用空间换时间的方式。这样优化后的时间复杂度为 O(n)，空间复杂度也为 O(n)。具体的实现代码如下：

def minSwapsCouples2(row):
    res = 0
    seatmap= [0 for _ in range(len(row))]
    for j in range(len(row)):
        # 序号为row[j]的人的座位号为j
        seatmap[row[j]] = j 

    for i in range(0, len(row), 2):
        # 得到row[i]对应的情侣编号
        x = row[i]^1
        if x == row[i+1]:
            continue
        # 找到序号为x的人对应的座位号
        index = seatmap[x]
        # 交换座位使情侣坐一起
        row[i+1], row[index] = row[index], row[i+1]
        # 更新seatmap，序号为row[index]的人现在在index上
        seatmap[row[index]] = index
        # 对于编号为x人交换到了i+1，这个动作可以不做，因为已经配对后续不会再找编号为x的人
        # seatmap[x] = i + 1
        res += 1
    return res

3. 分发糖果

这题是 leetcode 算法部分的135题，难度级别为困难。题目描述如下：

老师给孩子们分发糖果，有 N 个孩子站成了一条直线，老师根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果；

• 相邻的孩子中，评分高的孩子必须获得更多的糖果；

• 那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1：

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2：

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

对于这题，官方给出了 4 种解法，其中解法 2 是使用了贪心算法的思想。现在我们重点介绍下官方的解法 2 以及其贪心点。

在解法 2 中，使用两个一维数组 left 和 right。数组 left 用来存储每名学生只与左边邻居有关的所需糖果数。也就是假设规则为：如果一名学生评分比他左边学生高，那么他应该比他左边学生得到更多糖果。类似的，right 数组用来保存只与右边邻居有关的所需糖果数。也就是假设规则为：如果一名学生评分比他右边学生高，那么他应该比他右边学生得到更多糖果。

首先，在 left 和 right 数组中，给每个学生 1 个糖果。然后从左向右遍历整个数组，只要当前学生评分比他左邻居高，我们在 left 数组中更新当前学生的糖果数 left[i] = left[i-1] + 1，这是因为在每次更新前，当前学生的糖果数一定小于等于他左邻居的糖果数。

接下来用同样的方法从右到左，只要当前学生的评分比他右边（第 i+1 个）学生高，就更新 right[i] 为 right[i] = right[i + 1] + 1。现在，对于数组中第 i 个学生，为了满足题中条件，我们需要给他 max(left[i], right[i]) 个糖果。因此，最后我们得到最少糖果数：

最少糖果数 = $\sum^{n-1}_{i=0}max(left[i], right[i])$，其中， nn 是评分数组的长度。

上述算法在遍历过程中，每一步都尽量少给糖，必须加的时候加一个，这便体现了贪心思想：且在每次选择时，以局部最优为导向，而不考虑此次操作对以后操作的影响。有了上面的题解思路，我们的 Python 的代码就能理解写出，如下：

def candy(ratings):
    # 初始化值
    left = [1] * len(ratings)
    right = [1] * len(ratings)
    # 从左到右，只要当前学生评分比他左邻居高，则该学生糖果数相比左邻居加1
    for i in range(1, len(ratings)):
        if ratings[i] > ratings[i - 1]:
            left[i] = left[i - 1] + 1
    # 从右到左，只要当前学生评分比他右邻居高，则该学生糖果数相比右邻居加1
    for i in range(len(ratings) - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            right[i] = right[i + 1] + 1
    # 最后得到最少糖果数
    return sum([max(left[i], right[i]) for i in range(len(ratings))])

这里的贪心过程会有些难以理解，需要仔细揣摩。

4. 小结

本小节继续实战了贪心算法相关的编程题，这一次难度相比上一节有所加深。在 leetcode 上大约 80 道标签为贪心算法的编程题，解题思路都是类似的。再掌握了贪心的解题思路后，大家可以多多尝试解答 leetcode 上的其他编程题，达到熟能生巧的地步。