LeetCode - 1705 吃苹果的最大数目

向右看齐 2023-09-23 13:52 120阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

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

### 题目描述 ###

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

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

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

### 示例 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:54px;">输入</td> 
   <td style="width:444px;">apples = [1,2,3,5,2], days = [3,2,1,4,2]</td> 
  </tr> 
  <tr> 
   <td style="width:54px;">输出</td> 
   <td style="width:444px;">7</td> 
  </tr> 
  <tr> 
   <td style="width:54px;">解释</td> 
   <td style="width:444px;">你可以吃掉 7 个苹果：<br> - 第一天，你吃掉第一天长出来的苹果。<br> - 第二天，你吃掉一个第二天长出来的苹果。<br> - 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长&nbsp; 出来的苹果就已经腐烂了。<br> - 第四天到第七天，你吃的都是第四天长出来的苹果。</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>输入</td> 
   <td>apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]</td> 
  </tr> 
  <tr> 
   <td>输出</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>解释</td> 
   <td>你可以吃掉 5 个苹果：<br> - 第一天到第三天，你吃的都是第一天长出来的苹果。<br> - 第四天和第五天不吃苹果。<br> - 第六天和第七天，你吃的都是第六天长出来的苹果。</td> 
  </tr> 
 </tbody> 
</table>

### 提示 ###

*  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;
    };

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

![eb8d368ebfe34fee97a4e5e9f3707147.png][]

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

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

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

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

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

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

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

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

![e6f609b9334e4eaab2359a99d0a04bcc.png][]

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

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

![bff23546e51040beb7acba20668eacb0.png][]

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

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

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

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

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

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

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

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

![e399ae25e8da4bab8be8a0ee15d99f22.png][]

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

![df8bb0f41db544ea96022a74f62da761.png][]

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

![4320fc2bce93451b8496ceb997449cde.png][]

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

![7f434f0ef39a42d18a129a4a72a21c52.png][]

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

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

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

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

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

![9f7f052894d943bfab6b390c756a8a9b.png][]

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

![ca465e451a474793a5d476403ba75ee8.png][]

![7cd63c3a786142e9b620d9e24fc365fb.png][]

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

![f2d6a187220e4fdab4489ed862af3350.png][]

![170bc28f46ff439b95cbfa643dcbba19.png][]

当下沉到没有左右孩子，或者大于等于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();
      }
    }

![3c9336847db640edaa006089d183701a.png][]

[1705. _ - _LeetCode]: https://leetcode.cn/problems/maximum-number-of-eaten-apples/
[eb8d368ebfe34fee97a4e5e9f3707147.png]: https://img-blog.csdnimg.cn/eb8d368ebfe34fee97a4e5e9f3707147.png
[e6f609b9334e4eaab2359a99d0a04bcc.png]: https://img-blog.csdnimg.cn/e6f609b9334e4eaab2359a99d0a04bcc.png
[bff23546e51040beb7acba20668eacb0.png]: https://img-blog.csdnimg.cn/bff23546e51040beb7acba20668eacb0.png
[e399ae25e8da4bab8be8a0ee15d99f22.png]: https://img-blog.csdnimg.cn/e399ae25e8da4bab8be8a0ee15d99f22.png
[df8bb0f41db544ea96022a74f62da761.png]: https://img-blog.csdnimg.cn/df8bb0f41db544ea96022a74f62da761.png
[4320fc2bce93451b8496ceb997449cde.png]: https://img-blog.csdnimg.cn/4320fc2bce93451b8496ceb997449cde.png
[7f434f0ef39a42d18a129a4a72a21c52.png]: https://img-blog.csdnimg.cn/7f434f0ef39a42d18a129a4a72a21c52.png
[9f7f052894d943bfab6b390c756a8a9b.png]: https://img-blog.csdnimg.cn/9f7f052894d943bfab6b390c756a8a9b.png
[ca465e451a474793a5d476403ba75ee8.png]: https://img-blog.csdnimg.cn/ca465e451a474793a5d476403ba75ee8.png
[7cd63c3a786142e9b620d9e24fc365fb.png]: https://img-blog.csdnimg.cn/7cd63c3a786142e9b620d9e24fc365fb.png
[f2d6a187220e4fdab4489ed862af3350.png]: https://img-blog.csdnimg.cn/f2d6a187220e4fdab4489ed862af3350.png
[170bc28f46ff439b95cbfa643dcbba19.png]: https://img-blog.csdnimg.cn/170bc28f46ff439b95cbfa643dcbba19.png
[3c9336847db640edaa006089d183701a.png]: https://img-blog.csdnimg.cn/3c9336847db640edaa006089d183701a.png