LeetCode - 1705 吃苹果的最大数目

目录

题目来源

题目描述

示例

提示

题目解析

算法源码

---

题目来源

1705. 吃苹果的最大数目 - 力扣（LeetCode）

题目描述

有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。

你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。

给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。

示例

提示

• apples.length == n
• days.length == n
• 1 <= n <= 2 * 10^4
• 0 <= apples[i], days[i] <= 2 * 10^4
• 只有在 apples[i] = 0 时，days[i] = 0 才成立

题目解析

本题的解题思路其实就是贪心思维。

比如你手上有两包临期薯片A和B，假设A薯片明天过期，B薯片后天过期，你一天只能吃一包，那么你如何吃才能吃的多，且不会吃到过期薯片呢？

答案很简单，先吃快要过期。

即今天吃A薯片，明天吃B薯片，这样的话，就都赶在每包薯片过期前吃完了。

如果你今天吃B薯片，则明天你就不能吃A薯片了，因为明天时，A薯片就过期了。

本题比上面的情况要复杂一点，那就是每天都有新的临期薯片加入，因此每当有新的临期薯片加入时，我们就需要重新将薯片按照过期时间由近到远进行排序，先吃快要过期的。

这就是本题的解题思路。

最终代码实现如下

/**
 * @param {number[]} apples
 * @param {number[]} days
 * @return {number}
 */
var eatenApples = function (apples, days) {
  const pq = [];
  let count = 0;
 
  let i = 0;
  while (i < apples.length || pq.length !== 0) { // 注意即使没有新苹果的加入，存货苹果还是可能存在未腐烂的
    if (apples[i] > 0) {
      pq.push({
        apple: apples[i],
        day: i + days[i],
      });
      pq.sort((a, b) => a.day - b.day); // 过期时间排序
    }
 
    while (true) {
      if (pq.length === 0) break;
      let head = pq[0];
      if (head.day <= i || head.apple === 0) { // 如果过期了，或者没了，则出队
        pq.shift();
        continue;
      } else {
        head.apple--;
        count++;
        break;
      }
    }
 
    i++;
  }
 
  return count;
};

但是上面这种算法的性能非常低

上面程序中pq就是一个优先队列，pq中的元素都有一个优先级，优先级高的会先出队。在本题中，过期时间越近，即day越小，则优先级越高。

而上面程序中，pq的优先队列是基于有序数组实现的，这意味着每次有新元素加入，pq都需要经历至少O(n)时间才能保持优先队列的特性。

因此，算法的整体时间复杂度就会达到O(n^2)，而1 <= n <= 2 * 10^4，因此上面算法的性能就非常低了。

因此，我们需要优化优先队列的实现。

优先队列其实并不需要维护成一个严格有序的数组，这样的成本是极高的。优先队列的特性是每次出队时，都让优先级高的出队，因此我们只需要保证队头元素优先级最高即可。

优先队列通常采用堆结构来实现，所谓堆结构，即一颗完全二叉树。

那么什么是完全二叉树呢？

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

由上图我们可知，完全二叉树的最深的一层如果节点不满的话，则会优先填满左边。 

并且完全二叉树中某节点的序号为k的话，则其左孩子节点的序号必然为2k+1，其右孩子节点的序号必然为2k+2。因此上面的完全二叉树可以用数组来进行模拟：

可以发现数组的索引刚好就是完全二叉树节点的序号。 

堆结构对应的完全二叉树需要满足以下两个条件之一：

• 父节点要大于或等于其左右孩子节点，此时堆称为最大堆
• 父节点要小于或等于其左右孩子节点，此时堆称为最小堆

这样的话，堆结构才能快速地找到最值节点，即堆结构的顶点。

堆结构模拟优先队列，主要就是实现优先队列的入队和出队操作。

当我们向堆结构中入队一个新元素，需要先将新元素加入到堆结构对应的数组的尾部，但是这样的话可能会破坏堆结构的顺序性，因此我们需要通过上浮操作，来调整堆的顺序。

关于上浮操作，请看下面示例：

如下图，是一个最大堆，父节点的值总是大于其左右子孩子节点的值

 现在我们需要向堆中新增一个元素29，则先放在尾部，假设此时29的序号为k，则其父节点的序号必然为 Math.floor((k-1)/2)

然后比较29和其父节点值得大小，如果29 > 父节点值，则交换节点的值，完成29的上浮行为

然后继续比较，29和其父节点值的大小， 如果29 > 父节点值，则交换节点的值，完成29的上浮行为

直到，29发现其小于等于父节点值时，停止上浮，或者29已经上浮到k=0序号位置，即顶点位置时，停止上浮。

当我们需要优先队列出队时，即出队头，此时相当于堆结构删除堆顶元素，但是我们不能冒失的直接将堆顶元素删除，这样会让堆结构散架。

好的做法，是将堆顶元素和堆尾元素值交换，然后将堆尾元素弹出（堆结构可以用数组模拟，因此可以使用pop操作） ，但是此时堆顶元素的值其实并非最大值，因此我们需要使用下沉操作来调整堆结构，维护其顺序性。

关于下沉操作，我们可以看如下示例：

下图是一个最大堆，我们现在需要删除堆顶30

 则第一步是交换堆顶元素和堆尾元素的值，然后将堆尾元素弹出

此时最大堆的顺序性被破坏，我们开始执行下沉操作，所谓下沉操作，即将破坏顺序性的节点12和max(左孩子值，右孩子值) 比较，若12< max(左孩子值，右孩子值)，则交换

当下沉到没有左右孩子，或者大于等于max(左孩子，右孩子)时，即停止下沉。

我们可以发现，使用堆结构模拟的优先队列，每次入队都会触发上浮操作，每次出队都会触发下沉操作，但是上浮和下沉的次数最多就是完全二叉树的深度，而完全二叉树的深度为logN，也就是说堆结构维护的优先队列每次入队和出队的时间复杂度为O(logN)，这要比使用有序数组维护的优先队列的入队出队的时间复杂度O(n)，大大提升了效率。 

在Java语言中已经提供了实现好的优先队列工具类，但是在JavaScript语言中并没有，因此我们需要自己实现一个优先队列。大家可以参考下面算法源码中MyPriorityQueue类的实现。 

算法源码

/**
 * @param {number[]} apples
 * @param {number[]} days
 * @return {number}
 */
var eatenApples = function (apples, days) {
  const pq = new MyPriorityQueue((a, b) => a.day - b.day);
  let count = 0;
 
  let i = 0;
  while (i < apples.length || !pq.isEmpty()) {
    if (apples[i] > 0) {
      pq.push({
        apple: apples[i],
        day: i + days[i],
      });
    }
 
    while (true) {
      if (pq.isEmpty()) break;
      let head = pq.top();
      if (head.day <= i || head.apple === 0) {
        pq.shift();
        continue;
      } else {
        head.apple--;
        count++;
        break;
      }
    }
 
    i++;
  }
 
  return count;
};
 
class MyPriorityQueue {
  constructor(compare) {
    this.queue = [];
    this.compare = compare;
  }
 
  swap(i, j) {
    let tmp = this.queue[i];
    this.queue[i] = this.queue[j];
    this.queue[j] = tmp;
  }
 
  top() {
    return this.queue[0];
  }
 
  /* 判断队是否为空 */
  isEmpty() {
    return this.queue.length === 0;
  }
 
  /* 上浮 */
  swim() {
    let child = this.queue.length - 1;
    while (child !== 0) {
      let father = Math.floor((child - 1) / 2);
      if (this.compare(this.queue[child], this.queue[father]) < 0) {
        this.swap(child, father);
        child = father;
      } else {
        break;
      }
    }
  }
 
  /* 下沉 */
  sink() {
    let k = 0;
    while (true) {
      let l = 2 * k + 1;
      let r = l + 1;
 
      let K = this.queue[k];
      let L = this.queue[l];
      let R = this.queue[r];
 
      let t;
      if (L && R) {
        this.compare(L, R) > 0 ? (t = r) : (t = l);
      } else if (L && !R) {
        t = l;
      } else if (!L && R) {
        t = r;
      } else {
        break;
      }
 
      let T = this.queue[t];
      if (this.compare(T, K) < 0) {
        this.swap(t, k);
        k = t;
      } else {
        break;
      }
    }
  }
 
  /* 入队 */
  push(ele) {
    this.queue.push(ele);
    this.swim();
  }
 
  /* 出队 */
  shift() {
    this.swap(0, this.queue.length - 1);
    this.queue.pop();
    this.sink();
  }
}