分发糖果

LeetCode-135

/**
 * 时间复杂度O(n)
 * 贪心算法
 * 1. 将每个孩子都给一个初始值为1的糖果
 * 2. 从左往右遍历一次数组，如果当前位置的评分rating比前面位置的评分高，那么它所对应的糖果数量应当比前面位置多1个，否则糖果数量不变
 * 3. 再从右往左遍历一次数组，如果当前位置的评分rating比后面位置的评分高，并且它所对应的糖果数量不大于后面位置的糖果数量，那么它所对应的糖果数量应当是后面位置的糖果数量加1
 *
 * 先保证了相邻位置评分高的孩子糖果更多的要求，然后通过从右往左遍历数组来保证最小化糖果数量的要求，
因为在从右往左遍历时，我们可以保证每个孩子既满足相邻位置评分高的孩子糖果更多的要求，又尽量少地增加糖果数量，即可得到最优解
 */
var candy = function (ratings = []) {
  let n = ratings.length
  let candies = new Array(n).fill(1) // 先满足最小为1的糖果数
  let result = 0
  // 从左往右遍历(满足相邻糖果数多的要求)
  for (let i = 1; i < n; i++) {
    // 如果分数大于前一个，则比前一个小朋友多一个糖果
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1
    }
  }
  console.log(candies)
  // 从右往左遍历(调整：满足相邻糖果数多的要求. 例如用例: [5, 3, 4, 6, 2])
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
      candies[i] = candies[i + 1] + 1
    }
  }
  // 计算糖果总数
  for (let candy of candies) {
    result += candy
  }
  return result
}

console.log(candy([1, 2, 3, 4]))