带你读《图解算法小抄》二十二、贪心算法（4）

带你读《图解算法小抄》二十二、贪心算法（3）https://developer.aliyun.com/article/1347851?groupCode=tech_library

4.加油站

1）题目描述

给定一个环形路线上的加油站数组 gas 和消耗汽油的数组 cost，其中 gas[i] 表示第 i 个加油站的汽油量，cost[i] 表示从第 i 个加油站前往下一个加油站所需的汽油量。

你的任务是找到一个出发加油站的索引，使得从该加油站出发能够环绕一圈并返回起始加油站，并且在整个过程中汽油剩余量不会为负数。如果不存在这样的加油站，返回 -1。

2）解题步骤

为了解决加油站问题，我们可以使用贪心算法来解决。

• 初始化两个变量 totalGas 和 currentGas，分别表示加油站总的汽油量和当前汽油剩余量，初始值都为 0。
  
• 初始化一个变量 start，表示出发加油站的索引，初始值为 0。
  
• 遍历加油站数组 gas 和消耗数组 cost，计算累计汽油剩余量和总的汽油量：
  
• 将当前加油站的汽油量加到 totalGas 上。
  
• 将从当前加油站前往下一个加油站所需的汽油量加到 currentGas 上。
  
• 如果 currentGas 小于 0，表示从当前加油站出发无法到达下一个加油站，因此将出发加油站设为下一个加油站，并将 currentGas 重置为 0。
  

• 遍历结束后，判断 totalGas 是否大于等于 currentGas，如果是，则返回出发加油站的索引；否则，返回 -1。
  

下面是使用贪心算法解决加油站问题的算法框架：

function canCompleteCircuit(gas, cost) {
  let totalGas = 0;
  let currentGas = 0;
  let start = 0;  for (let i = 0; i < gas.length; i++) {
    totalGas += gas[i];
    currentGas += gas[i] - cost[i];    if (currentGas < 0) {
      start = i + 1;
      currentGas = 0;
    }
  }
  return totalGas >= currentGas ? start : -1;
}

5.根据身高重建队列

1）题目描述

假设有打乱顺序的一群人站成一个队列。每个人由一个整数对 (h, k) 表示，其中 h是这个人的身高，k 是前面身高大于或等于 h 的人数。编写一个算法来重建队列。

注意：

总人数少于 1100 人。

2）解题步骤

为了解决根据身高重建队列的问题，我们可以使用贪心算法来解决。贪心算法的思路是先安排身高较高的人，然后再依次插入身高较矮的人，使其满足前面身高大于或等于 h的人数的要求。

我们按照以下步骤进行解题：

• 将所有人按照身高 h 进行降序排序，如果身高相同，则按照 k 进行升序排序。
  
• 创建一个空数组 result 用于存储重建后的队列。
  
• 遍历排序后的人员列表，对于每个人 (h, k)：
  
• 将其插入到 result 数组的索引 k 的位置，这样可以确保前面的人数大于或等于 k。
  
• 返回重建后的队列 result。
  

以下是使用贪心算法解决根据身高重建队列问题的算法框架：

function reconstructQueue(people) {
  people.sort((a, b) => {
    if (a[0] === b[0]) {
      return a[1] - b[1];
    }
    return b[0] - a[0];
  });  const result = [];  for (let i = 0; i < people.length; i++) {
    result.splice(people[i][1], 0, people[i]);
  }
  return result;
}

带你读《图解算法小抄》二十二、贪心算法（5）https://developer.aliyun.com/article/1347849?groupCode=tech_library