135. 分发糖果

分类 - 力扣题解 共有 0 条评论

Problem: 135. 分发糖果

思路

根据题意可以得知：每个孩子所需要的最小糖果数量只与他左右孩子的评分有关。
对于每个孩子 $i$ 他的左右孩子评分类型只有 $9$ 种，如下图所示：

image.png

根据上面的分析，当前孩子最小糖果数量如果与其他孩子有关，那么一定是与比他评分小的孩子有关。所以我们需要先计算评分小的孩子的最小糖果数量，才能推算出评分大的孩子的最小糖果数量。

可以用一个数组存储每个孩子的最小糖果数量，最后加起来即为结果。

需要考虑只有一个孩子的情况，一个孩子直接返回 1 即可。

具体过程

举个例子：

以此数据为例：$[29,51,87,87,72]$
image.png

  1. 首先我们将这组数据的值和下标存入 MAP 中，可以存一个二维数组，方便后续取值。第一个值代表评分，第二个值代表是第几个孩子，并使用一个数组将 key 排序，这是为了先找到评分低的孩子，即：

     map:{
     29: [[29,0]],
     51: [[51,1]],
     87: [[87,2],[87,3]],
     72: [[72,4]]
     }
 keys: [29,51,72,87]
  2. 使用一个循环，依次取出 keys 中最小的那个，在 map 中将对应的评分取出来，设为 minRatings。

  3. 循环遍历 minRatings，根据上面 9 种类型，判断当前孩子的最小糖果数量。因为这 9 种情况最小考虑的孩子数量是三个，所以需要单独处理下面 a, b 两种边界情况，即第一个孩子和最后一个孩子，这两种情况的最小糖果数量为 1。

    1. 如果是第一个孩子，且他右边孩子评分数量大于他。
    2. 如果是第最后一个孩子，且他左边孩子评分数量大于他。

以下是循环过程：

假设最小糖果数量数组为 countArray。

第一次：取出 29:[29,0]，符合 3.a，$countArray[0] = 1$
第二次：取出 51:[51,1]，符合 情况 6 ，$countArray[1] = countArray[0]+ 1 = 1 + 1 = 2$
第三次：取出 72:[72,4]，符合 3.b，$countArray[4] = 1$
第四次：取出 81: [[87,2],[87,3]]，分别符合情况 3 和 7，$countArray[2] = countArray[1]+ 1 = 2 + 1 = 3$ $countArray[3] = countArray[4]+ 1 = 1 + 1 = 2$

即 countArray: [1,2,3,2,1]，求和即为结果 9。

Code

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function (ratings) {
  if (ratings.length === 1) {
    return 1;
  }
  let hashmap = new Map();
  ratings.forEach((v, i) => {
    if (hashmap.has(v)) {
      hashmap.get(v).push([v, i]);
    } else {
      hashmap.set(v, [[v, i]]);
    }
  });
  let hashmapArray = [];
  for (let i of hashmap.keys()) {
    hashmapArray.push(i);
  }
  hashmapArray.sort((a, b) => a - b);
  let countArray = new Array(ratings.length);
  while (hashmapArray.length > 0) {
    let minRating = hashmapArray.shift();
    let minRatings = hashmap.get(minRating);
    for (let item of minRatings) {
      let i = item[1];
      let v = item[0];
      if (
        (i === 0 && ratings[i + 1] >= v) ||
        (i === ratings.length - 1 && ratings[i - 1] >= v) ||
        (ratings[i - 1] >= v && ratings[i + 1] >= v)
      ) {
        countArray[i] = 1;
      } else {
        let l = ratings[i - 1];
        let r = ratings[i + 1];
        if (l < v && r < v) {
          countArray[i] = Math.max(countArray[i - 1], countArray[i + 1]) + 1;
        } else if (l < v) {
          countArray[i] = countArray[i - 1] + 1;
        } else {
          countArray[i] = countArray[i + 1] + 1;
        }
      }
    }
  }
  return countArray.reduce((p, c) => p + c);
};

本文由 suxi 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2024/03/26 20:41

← → ↓ ↑
文章评论