leetcode-1705.吃苹果的最大数目

发表于:2021-12-24 15:32
技术,算法,leetcode
热度:52
喜欢:0

有一棵特殊的苹果树,一连 n 天,每天都可以长出若干个苹果。在第 i 天,树上会长出 apples[i] 个苹果,

这些苹果将会在 days[i] 天后(也就是说,第 i + days[i] 天时)腐烂,变得无法食用。

也可能有那么几天,树上不会长出新的苹果,此时用 apples[i] == 0 且 days[i] == 0 表示。

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

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

示例 1:

输入:apples = [1,2,3,5,2], days = [3,2,1,4,2]
输出:7
解释:你可以吃掉 7 个苹果:

  • 第一天,你吃掉第一天长出来的苹果。
  • 第二天,你吃掉一个第二天长出来的苹果。
  • 第三天,你吃掉一个第二天长出来的苹果。过了这一天,第三天长出来的苹果就已经腐烂了。
  • 第四天到第七天,你吃的都是第四天长出来的苹果。

示例 2:

输入:apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
输出:5
解释:你可以吃掉 5 个苹果:

  • 第一天到第三天,你吃的都是第一天长出来的苹果。
  • 第四天和第五天不吃苹果。
  • 第六天和第七天,你吃的都是第六天长出来的苹果。
javascript 复制代码
/**
 * @param {number[]} apples
 * @param {number[]} days
 * @return {number}
 * @description 优先队列
 */
//  https://leetcode-cn.com/problems/maximum-number-of-eaten-apples/
var eatenApples = function (apples, days) {
  // 苹果堆
  let appleBuck = [];
  let totalDays = apples.length
  // 从第一天开始
  let i = 0;
  // 可以吃掉苹果的次数
  let canEatAppleDays = 0;
  while (i === 0 || appleBuck.length !== 0 || totalDays >= 0) {
    if (i < apples.length) {
      let appleNum = apples[i];
      // 添加apples[i]个 days[i]过期的苹果
      while (appleNum !== 0) {
        appleBuck.push(days[i]);
        appleNum--
      }
    }
    // 当前第几天,看看有没有苹果
    appleBuck = appleBuck.sort((a, b) => a - b);
    appleBuck = appleBuck.filter(e => e != 0);
    let canEatApple = false;

    if (appleBuck.length > 0) {
      canEatApple = true
      canEatAppleDays++
      appleBuck.shift();
    }

    appleBuck = appleBuck.map(e => e - 1)
    // console.log(`第${i + 1}天,今天${canEatApple ? '可以' : '不可以'},明天还有${appleBuck.length}个,`)
    totalDays--
    i++
    // console.log(i, appleBuck.length, totalDays)
  };
  // console.log(canEatAppleDays);
  return canEatAppleDays

};

var eatenApples2 = function (apples, days) {
  // 苹果堆
  let appleBuck = [];
  let totalDays = apples.length
  // 从第一天开始
  let i = 0;
  // 可以吃掉苹果的次数
  let canEatAppleNum = 0;

  while (i === 0 || appleBuck.length !== 0 || totalDays >= 0) {
    let newDayAppleNum;
    let newDayAppleLeftDay;
    let todayHasApple = false;
    // 补给天数内,还可以添加
    if (i < apples.length) {
      todayHasApple = apples[i] !== 0;
      newDayAppleNum = apples[i];
      newDayAppleLeftDay = days[i];
      // newDayApple = new Array(appleNum).fill(days[i])
      // 添加apples[i]个 days[i]过期的苹果
    }
    // console.log(`第${i + 1}天,今天${todayHasApple}`)

    if (todayHasApple) {
      let last0Index;
      let lastLessIndex;
      let newappleBuck = appleBuck;

      if (appleBuck.length === 0 && i < apples.length) {
        appleBuck = Array(newDayAppleNum).fill(newDayAppleLeftDay)
      } else {
        // console.log('appleBuck', appleBuck)
        for (let j = 0; j < appleBuck.length; j++) {
          // 今天的苹果,剩余的天数
          const leftDay = appleBuck[j];
          // 去掉0 
          if (last0Index === 0) {
            appleBuck.slice(j, 1);
          }
          // 最后一个小于当前剩余天数的索引
          // console.log('j', leftDay, newDayAppleNum)
          if (leftDay <= newDayAppleNum) {
            lastLessIndex = j;
          }
        }
        // 先插后截
        if (lastLessIndex) {
          newappleBuck = appleBuck.slice(0, lastLessIndex).concat(Array(newDayAppleNum).fill(newDayAppleLeftDay)).concat(appleBuck.slice(lastLessIndex, appleBuck.length))
        }
        appleBuck = newappleBuck;
        // console.log('appleBuck', appleBuck)

      }

    }
    // console.log(`第${i + 1}天,${appleBuck}`)
    let canEatApple = false;

    if (appleBuck.length > 0) {
      canEatApple = true
      canEatAppleNum++
      appleBuck.shift();
    }

    appleBuck = appleBuck.map(e => e - 1)
    // console.log(`第${i + 1}天,今天${canEatApple ? '可以' : '不可以'},明天还有${appleBuck.length}个,`)
    totalDays--
    i++
    // console.log(i, appleBuck.length, totalDays)
  };
  console.log('canEatAppleNum', canEatAppleNum);
  return canEatAppleNum
};
eatenApples2([1, 2, 3, 5, 2], [3, 2, 1, 4, 2])
// eatenApples2([3, 0, 0, 0, 0, 2], [3, 0, 0, 0, 0, 2])
// eatenApples([0, 149, 254, 74, 127, 86, 48, 217, 0, 11, 96, 158, 0, 167, 0, 0, 5, 73, 0, 35, 148, 0, 74, 261, 0, 0, 27, 67, 25, 46, 76, 43, 0, 0, 161, 44, 0, 148, 77, 0, 186, 228, 277, 270, 257, 242, 144, 74, 145, 84, 90, 0, 0, 0, 265, 224, 265, 86, 119, 0, 3, 0, 285, 16, 145, 212, 102, 0, 0, 0, 24, 0, 0, 136, 110, 264, 194, 0, 150, 0, 247, 0, 27, 46, 0, 118, 0, 178, 0, 0, 270, 58, 0, 109, 236, 0, 241, 241, 0, 111, 217, 252, 43, 46, 0, 0, 0, 30, 89, 0, 242, 121, 6, 0, 278, 228, 0, 119, 0, 226, 230, 0, 115, 0, 108, 167, 166, 0, 0, 110, 82, 289, 0, 13, 140, 79, 164, 0, 17, 133, 257, 68, 105, 0, 0, 0, 0, 114, 217, 37, 0, 23, 107, 74, 0, 167, 238, 0, 181, 259, 98, 0, 94, 268, 272, 0, 153, 249, 216, 0, 253, 277, 262, 229, 106, 257, 94, 154, 135, 23, 186, 0, 260, 0, 0, 252, 127, 253, 162, 18, 34, 235, 265, 35, 136, 5, 14, 132, 195, 60, 0, 0, 0, 0, 205, 277, 110, 222, 252, 16, 0, 2, 0, 227, 262, 128, 0, 76, 146, 203, 255, 0, 131, 0, 39, 110, 180, 0, 247, 49, 280, 30, 0, 283, 260, 258, 103, 231, 48, 166, 106, 33, 188, 210, 72, 52, 103, 0, 132, 129, 0, 74, 0, 0, 184, 0, 219, 164, 167, 146, 158, 77, 114, 265, 109, 223, 63, 62, 253, 0, 189, 276, 36, 129, 0, 206, 40, 0, 158, 10, 216, 13, 269, 0, 0, 0, 0, 172, 0, 0, 117, 265, 0, 177, 0, 281, 260, 0, 246, 120, 0, 46, 29, 0, 210, 0, 103, 287, 0, 61, 79, 0, 15, 0, 0, 0, 113, 0, 110, 186, 47, 137, 281, 251, 0, 184, 0, 0, 0, 204, 86, 0, 235, 43, 169, 248, 74, 269, 154, 113, 132, 213, 0, 0, 184, 0, 1, 266, 215, 156, 41, 79, 95, 0, 256, 166, 288, 0, 0, 177, 0, 0, 107, 17, 252, 137, 70, 11, 155, 105, 159, 121, 22, 0, 37, 59, 218, 231, 49, 64, 14, 0, 6, 46, 216, 0, 0, 2, 217, 0, 118, 102, 260, 0, 210, 275, 221, 0, 0, 92, 42, 31, 0, 0, 43, 108, 277, 0, 23, 198, 51, 284, 64, 9, 0, 89, 167, 256, 217, 27, 197, 232, 202, 0, 77, 217, 132, 182, 20, 186, 0, 0, 62, 0, 0, 0, 10, 40, 131, 274, 0, 221, 0, 0, 0, 159, 244, 252, 268, 234, 171, 0, 0, 146, 155, 0, 241, 179, 199, 0, 211, 265, 12, 0, 0, 90, 7, 40, 139, 203, 0, 245, 210, 0, 0, 74, 168, 213, 0, 0, 0, 80, 49, 0, 192, 0, 111, 27, 204, 0, 234, 0, 223, 242, 202, 116, 112, 281, 0, 168, 218, 214, 271, 240, 249, 13, 235, 194, 74, 0, 24, 226, 204, 248, 280, 122, 122, 148, 194, 0, 212, 0, 106, 192, 0, 241, 153, 0, 0, 109, 0, 44, 0, 0, 54, 0, 0, 12, 0, 202, 13, 44, 266, 37, 0, 0, 0, 167, 266, 79, 290, 65, 179, 258, 280, 0, 0, 93, 165, 117, 0, 287, 0, 0, 0, 23, 255, 8, 141, 0, 105, 198, 53, 104, 136, 195, 202, 70, 11, 90, 126, 88, 253, 0],
// [0, 90, 407, 127, 168, 55, 29, 409, 0, 15, 154, 286, 0, 50, 0, 0, 3, 108, 0, 66, 279, 0, 75, 352, 0, 0, 38, 127, 2, 62, 78, 21, 0, 0, 56, 68, 0, 43, 102, 0, 245, 247, 363, 377, 137, 90, 159, 129, 115, 107, 31, 0, 0, 0, 222, 43, 29, 160, 206, 0, 1, 0, 517, 29, 213, 96, 141, 0, 0, 0, 28, 0, 0, 205, 133, 525, 47, 0, 189, 0, 384, 0, 54, 25, 0, 58, 0, 235, 0, 0, 299, 63, 0, 54, 346, 0, 27, 299, 0, 81, 36, 503, 54, 3, 0, 0, 0, 11, 21, 0, 442, 61, 11, 0, 286, 193, 0, 230, 0, 191, 266, 0, 167, 0, 26, 190, 100, 0, 0, 213, 164, 325, 0, 11, 271, 128, 186, 0, 29, 54, 45, 122, 81, 0, 0, 0, 0, 76, 102, 55, 0, 33, 12, 138, 0, 32, 4, 0, 68, 196, 87, 0, 162, 473, 451, 0, 20, 434, 182, 0, 498, 527, 332, 329, 41, 165, 169, 68, 226, 33, 344, 0, 65, 0, 0, 193, 236, 42, 248, 31, 63, 70, 212, 49, 43, 4, 10, 159, 19, 110, 0, 0, 0, 0, 88, 58, 89, 132, 118, 20, 0, 2, 0, 248, 92, 252, 0, 41, 287, 4, 350, 0, 26, 0, 32, 75, 295, 0, 296, 92, 557, 37, 0, 103, 31, 271, 200, 95, 9, 187, 115, 43, 225, 154, 100, 8, 92, 0, 70, 237, 0, 124, 0, 0, 199, 0, 290, 18, 284, 85, 128, 40, 71, 111, 108, 319, 20, 70, 121, 0, 354, 441, 58, 20, 0, 370, 66, 0, 152, 5, 245, 20, 220, 0, 0, 0, 0, 176, 0, 0, 7, 518, 0, 101, 0, 216, 166, 0, 341, 66, 0, 88, 46, 0, 409, 0, 133, 178, 0, 36, 71, 0, 4, 0, 0, 0, 139, 0, 15, 296, 31, 112, 89, 184, 0, 210, 0, 0, 0, 227, 89, 0, 2, 67, 15, 209, 109, 413, 83, 179, 58, 313, 0, 0, 72, 0, 1, 102, 78, 160, 65, 139, 61, 0, 257, 95, 397, 0, 0, 169, 0, 0, 25, 30, 27, 135, 90, 4, 129, 160, 311, 139, 16, 0, 7, 87, 383, 154, 92, 97, 2, 0, 3, 34, 65, 0, 0, 2, 319, 0, 23, 8, 432, 0, 106, 113, 72, 0, 0, 62, 17, 59, 0, 0, 79, 136, 35, 0, 41, 167, 21, 313, 1, 2, 0, 62, 330, 403, 328, 28, 370, 308, 87, 0, 151, 78, 105, 305, 20, 10, 0, 0, 12, 0, 0, 0, 12, 76, 228, 382, 0, 336, 0, 0, 0, 178, 242, 418, 323, 436, 296, 0, 0, 81, 5, 0, 365, 22, 268, 0, 217, 451, 7, 0, 0, 111, 11, 25, 81, 400, 0, 151, 290, 0, 0, 66, 334, 259, 0, 0, 0, 41, 52, 0, 151, 0, 119, 40, 398, 0, 118, 0, 252, 86, 79, 29, 201, 548, 0, 111, 98, 134, 460, 89, 488, 20, 67, 123, 43, 0, 37, 140, 71, 93, 114, 171, 111, 228, 278, 0, 173, 0, 188, 211, 0, 106, 276, 0, 0, 205, 0, 44, 0, 0, 64, 0, 0, 11, 0, 233, 3, 10, 526, 49, 0, 0, 0, 171, 252, 33, 413, 48, 264, 348, 67, 0, 0, 122, 153, 3, 0, 180, 0, 0, 0, 19, 370, 7, 218, 0, 5, 34, 77, 132, 115, 143, 94, 77, 18, 75, 232, 162, 227, 0])

// eatenApples2([243, 103, 0, 243, 289, 5, 72, 0, 17, 201, 0, 132, 0, 262, 0, 248, 200, 168, 295, 237, 69, 49, 52, 0, 188, 255, 168, 0, 0, 92, 258, 95, 0, 115, 0, 131, 111, 12, 0, 85, 91, 0, 111, 228, 0, 0, 244, 33, 252, 0, 160, 0, 277, 0, 0, 0, 40, 68, 210, 122, 220, 94, 164, 0, 0, 0, 28, 96, 0, 284, 165, 0, 0, 231, 295, 246, 208, 0, 277, 220, 125, 235, 199, 0, 35, 303, 32, 192, 267, 98, 288, 0, 81, 14, 45, 246, 203, 0, 256, 105, 147, 294, 165, 107, 257, 173, 277, 0, 0, 0, 215, 300, 117, 302, 0, 90, 0, 245, 0, 0, 107, 278, 166, 30, 281, 169, 178, 300, 90, 112, 27, 0, 162, 12, 226, 9, 235, 139, 273, 1, 0, 0, 265, 0, 239, 283, 204, 22, 200, 295, 0, 0, 0, 0, 0, 0, 148, 0, 57, 116, 143, 132, 201, 56, 102, 55, 0, 255, 298, 197, 81, 187, 82, 149, 212, 284, 0, 0, 75, 0, 233, 0, 67, 212, 196, 0, 165, 102, 101, 195, 104, 0, 227, 0, 270, 0, 0, 283, 1, 137, 0, 302, 62, 0, 127, 293, 182, 232, 0, 0, 137, 0, 0, 0, 98, 0, 83, 52, 0, 0, 280, 262, 24, 252, 173, 20, 236, 30, 87, 103, 0, 147, 194, 55, 152, 209, 0, 0, 110, 232, 108, 104, 90, 0, 229, 123, 110, 183, 231, 20, 134, 0, 0, 220, 193, 254, 104, 227, 0, 20, 233, 0, 55, 0, 54, 1, 0, 247, 0, 0, 0, 0, 33, 171, 19, 86, 12, 69, 0, 70, 139, 0, 125, 193, 58, 196, 109, 0, 68, 98, 0, 0, 222, 98, 0, 111, 0, 0, 0, 0, 0, 0, 214, 227, 94, 249, 0, 0, 235, 165, 221, 78, 174, 0, 163, 49, 155, 188, 189, 173, 0, 162, 0, 98, 181, 117, 50, 300, 253, 272, 210, 0, 93, 40, 46, 0, 203, 92, 193, 237, 194, 0, 127, 0, 11, 101, 201, 0, 0, 33, 129, 304, 0, 86, 0, 79, 0, 0, 260, 142, 68, 0, 243, 0, 0, 241, 224, 4, 192, 252, 0, 295, 106, 191, 292, 49, 0, 138, 0, 141, 140, 205, 262, 236, 206, 27, 22, 172, 142, 219, 123, 70, 200, 270, 17, 136, 80, 0, 209, 0, 67, 143, 0, 152, 230, 0, 72, 175, 130, 191, 291, 0, 84, 48, 250, 0, 174, 0, 0, 0, 0, 293, 75, 0, 9, 179, 0, 206, 0, 189, 61, 0, 138, 146, 83, 170, 157, 64, 0, 0, 266, 274, 0, 229, 32, 115, 176, 298, 0, 78, 235, 0, 215, 245, 95, 101, 265, 0, 0, 15, 0, 140, 0, 237, 202, 167, 19, 0, 83, 0, 172, 304, 0, 149, 186, 1, 0, 0, 70, 129, 60, 293, 0, 125, 0, 0, 39, 24, 10, 111, 161, 5, 0, 15, 93, 0, 281, 37, 222, 263, 0, 291, 6, 225, 226, 230, 296, 40, 251, 75, 40, 0, 188, 0, 0, 271, 0, 0, 87, 76, 164, 0, 4, 43, 74, 11, 51, 0, 0, 298, 150, 190, 128, 168, 69, 0, 105, 223, 0, 136, 48, 196, 172, 0, 20, 93, 234, 0, 0, 193, 136, 36, 19, 235, 150, 197, 117, 2, 54, 0, 5, 0, 0, 158, 46, 0, 151, 211, 79, 0, 280, 179, 153, 0, 0, 215, 0, 114, 217, 243, 0, 0, 279, 223, 254, 65, 213, 0, 280, 0, 280, 118, 16, 0, 179, 0, 88, 92, 251, 217, 0, 0, 107, 109, 9, 158, 139, 259], [482, 141, 0, 72, 362, 3, 118, 0, 30, 170, 0, 23, 0, 291, 0, 53, 396, 23, 327, 106, 11, 13, 100, 0, 256, 23, 116, 0, 0, 107, 215, 160, 0, 180, 0, 120, 107, 6, 0, 165, 15, 0, 46, 133, 0, 0, 188, 17, 499, 0, 278, 0, 241, 0, 0, 0, 3, 72, 290, 20, 233, 93, 17, 0, 0, 0, 7, 64, 0, 568, 107, 0, 0, 156, 412, 233, 273, 0, 242, 304, 62, 223, 82, 0, 47, 383, 63, 3, 517, 44, 69, 0, 132, 13, 45, 83, 214, 0, 417, 75, 47, 63, 107, 190, 358, 240, 470, 0, 0, 0, 272, 78, 199, 204, 0, 51, 0, 350, 0, 0, 195, 523, 212, 6, 93, 214, 102, 29, 77, 208, 20, 0, 144, 8, 106, 12, 383, 106, 359, 1, 0, 0, 337, 0, 200, 126, 208, 38, 233, 474, 0, 0, 0, 0, 0, 0, 268, 0, 49, 123, 28, 191, 67, 30, 192, 91, 0, 13, 148, 173, 92, 51, 50, 190, 89, 301, 0, 0, 72, 0, 58, 0, 34, 18, 262, 0, 54, 58, 168, 370, 200, 0, 166, 0, 16, 0, 0, 225, 1, 215, 0, 302, 97, 0, 250, 256, 291, 64, 0, 0, 42, 0, 0, 0, 195, 0, 5, 86, 0, 0, 539, 59, 13, 304, 164, 23, 248, 53, 45, 165, 0, 104, 236, 55, 5, 252, 0, 0, 205, 395, 20, 171, 83, 0, 42, 237, 100, 133, 257, 21, 252, 0, 0, 328, 30, 302, 9, 110, 0, 26, 108, 0, 1, 0, 54, 2, 0, 239, 0, 0, 0, 0, 25, 219, 15, 64, 9, 62, 0, 62, 103, 0, 230, 161, 39, 307, 169, 0, 40, 115, 0, 0, 143, 170, 0, 72, 0, 0, 0, 0, 0, 0, 252, 244, 92, 12, 0, 0, 108, 58, 163, 84, 143, 0, 51, 67, 38, 30, 186, 287, 0, 322, 0, 156, 123, 197, 61, 230, 43, 79, 117, 0, 68, 4, 33, 0, 240, 88, 156, 84, 228, 0, 184, 0, 16, 64, 336, 0, 0, 14, 218, 285, 0, 77, 0, 46, 0, 0, 128, 159, 111, 0, 106, 0, 0, 274, 175, 5, 226, 9, 0, 144, 92, 165, 67, 48, 0, 256, 0, 7, 214, 333, 148, 55, 286, 20, 6, 277, 137, 189, 232, 32, 1, 108, 24, 128, 10, 0, 142, 0, 31, 78, 0, 254, 98, 0, 83, 11, 213, 105, 463, 0, 111, 26, 166, 0, 239, 0, 0, 0, 0, 456, 47, 0, 4, 311, 0, 405, 0, 71, 107, 0, 96, 27, 130, 200, 181, 40, 0, 0, 517, 64, 0, 179, 51, 45, 158, 151, 0, 100, 309, 0, 403, 107, 42, 193, 201, 0, 0, 23, 0, 10, 0, 199, 144, 44, 13, 0, 149, 0, 344, 118, 0, 155, 176, 2, 0, 0, 99, 80, 89, 369, 0, 161, 0, 0, 6, 45, 13, 218, 30, 1, 0, 25, 172, 0, 360, 49, 40, 468, 0, 238, 1, 243, 417, 147, 537, 3, 49, 128, 45, 0, 330, 0, 0, 367, 0, 0, 14, 62, 159, 0, 4, 48, 141, 19, 7, 0, 0, 570, 249, 312, 219, 40, 2, 0, 162, 65, 0, 129, 96, 126, 319, 0, 9, 107, 312, 0, 0, 20, 124, 4, 38, 219, 232, 340, 225, 4, 100, 0, 3, 0, 0, 77, 43, 0, 283, 96, 77, 0, 337, 126, 257, 0, 0, 327, 0, 124, 253, 478, 0, 0, 28, 119, 403, 58, 122, 0, 63, 0, 405, 198, 27, 0, 186, 0, 60, 57, 47, 56, 0, 0, 65, 203, 15, 118, 31, 415])