135.分发糖果

链接：135.分发糖果
难度：Hard
标签：贪心、数组
简介：老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。那么这样下来，老师至少需要准备多少颗糖果呢？。

题解 1 - typescript

• 编辑时间：2020-12-24
• 执行用时：88ms
• 内存消耗：43.2MB
• 编程语言：typescript
• 解法介绍：两次遍历取最大值。

function candy(ratings: number[]): number {
  const left: number[] = [];
  const len = ratings.length;
  for (let i = 0; i < len; i++) {
    if (i === 0 || ratings[i - 1] >= ratings[i]) {
      left[i] = 1;
    } else {
      left[i] = left[i - 1] + 1;
    }
  }
  let right = 1;
  let ans = 0;
  for (let i = len - 1; i >= 0; i--) {
    if (i === len - 1 || ratings[i + 1] >= ratings[i]) {
      right = 1;
    } else {
      right++;
    }
    ans += Math.max(right, left[i]);
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-07-21
• 执行用时：104ms
• 内存消耗：42.7MB
• 编程语言：typescript
• 解法介绍：从左往右遍历一遍，从右往左遍历一遍，取最大值。

function candy(ratings: number[]): number {
  const n = ratings.length;
  const l = new Array(n).fill(1);
  const r = new Array(n).fill(1);
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) l[i] = l[i - 1] + 1;
  }
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) r[i] = r[i + 1] + 1;
  }
  let ans = 0;
  for (let i = 0; i < n; i++) ans += Math.max(l[i], r[i]);
  return ans;
}