leetcode糖果问题，这种做法为什么可行?

Question

leetcode糖果问题，这种做法为什么可行?

leetcode糖果问题
这个官方题解并没有证明，只是说了一下过程。我有以下几点疑问：

• left[..]是在仅符合左规则下分的糖果最少的分配方案吗？同样的right[...]是在仅符合右规则下分的糖果最少的分配方案吗？
• 为什么取仅符合左规则的值和仅符合右规则的值的最大值可以同时符合左右规则呢?

• 就算符合左右规则，为什么这种方案下分的糖果是最少的呢?
  

  var candy = function(ratings) {
    const n = ratings.length;
    const left = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        if (i > 0 && ratings[i] > ratings[i - 1]) {
            left[i] = left[i - 1] + 1;
        } else {
            left[i] = 1;
        }
    }
  
    let right = 0, ret = 0;
    for (let i = n - 1; i > -1; i--) {
        if (i < n - 1 && ratings[i] > ratings[i + 1]) {
            right++;
        } else {
            right = 1;
        }
        ret += Math.max(left[i], right);
    }
    return ret;
  };

  附：
  我凭感觉也写了一种解法，通过了但是我并不知道这是否真的正确。如果是正确的，该怎么证明?如果是错误的，它哪里有问题?

  function candy(ratings) {
  /*
        candy[i] : the min number of candy the i th people can get
        
        based on ratings[0...i], we calculate candy[0...i]
        if we add ratings[i+1], how to calculate candy[0...i+1]
        guess(I don't know how to proof):
        1. ratings[i+1] > ratings[i], candy[i+1] = candy[i] + 1
        2. ratings[i+1] == ratings[i], candy[i+1] = 1
        3. ratings[i+1] < ratings[i]
            candy[i] > 1 => candy[i + 1] = 1
            candy[i] == 1 => candy[i] += 1, candy[i] = 1
                            => if ratings[i-1] > ratings[i], 
                            and candy[i-1] >=(actual = ) ratings[i]
                            candy[i-1] += 1 => ...   
        based on rating[0]
        candy[0] = 1
        
    */
  const n = ratings.length;
  const minCandies = Array(n).fill(1);
  
  for (let i = 1; i < n; ++i) {
    if (ratings[i] > ratings[i - 1]) {
      minCandies[i] = minCandies[i - 1] + 1;
    } else if (ratings[i] === ratings[i - 1]) {
      minCandies[i] = 1;
    } else {
      minCandies[i] = 1;
      if (minCandies[i - 1] == 1) {
        minCandies[i - 1]++;
        let cur = i - 1;
        while (
          cur - 1 >= 0 &&
          ratings[cur - 1] > ratings[cur] &&
          minCandies[cur - 1] <= minCandies[cur]
        ) {
          minCandies[cur - 1]++;
          cur--;
        }
      }
    }
  }
  return minCandies.reduce((pre, cur) => pre + cur);
  }

Answer 1

left[..]是在仅符合左规则下分的糖果最少的分配方案吗？同样的right[...]是在仅符合右规则下分的糖果最少的分配方案吗？

是

为什么取仅符合左规则的值和仅符合右规则的值的最大值可以同时符合左右规则呢?

如果 rating[i] < rating[i+1] ，那么 left[i] < left[i+1], right[i] = 1

最终结果是 candy[i] = max(left[i], right[i]) = max(left[i], 1) = left[i], candy[i+1] = max(left[i+1], righ[i+1]) >= left[i+1], 所以,candy[i] < cand[i+1]，满足要求。

大于的情况同上。

相等时任意方案均满足要求。

所以任意相邻两个，用 max(left, right) 均同时满足所有规则。

就算符合左右规则，为什么这种方案下分的糖果是最少的呢?

可以验证只有 1个，2个孩子时是最少的。

可以验证在 rating 严格单调增加于严格单调减小时是最少的。

可以验证，但序列先严格单调增加，再严格单调减小是最少的。
（比如，[1,4,5,3,2]。即存在 k , 对任意 0 < i < k ,有 rating[i-1] < rating[i] < rating[i+1]; 对任意 k < j < N-1 ， 有 rating[j-1] > rating[j] > rating[j+1]。

否则，利用数学归纳法，如果对 N 个及以下孩子时时最小的。对 N+1 个孩子的情况，除去以上讨论过的情形
1) 如果存在 k，使得 raing[k] == rating[k+1]，则整个问题可以拆解为 [0..k], [k+1..N] 两个子问题，长度分别为 k+1 与 N-k。两个区间内left, right, candy 的取值均互不影响。由归纳假设，可以得到最小值
2) 否则，则一定存在 k ，使得 rating[k-1] > rating[k] < rating[k+1]。 此时，可以令 candy[k] = 1。[0,k] 区间 与 [k,N] 区间相互独立，两个区间内left, right, candy 的取值均互不影响。于是这就形成了两个长度分别为 k+1 与 N-k+1 的子问题。由归纳假设，可知可以分别得到他们的最小值，于是对N+1 的情况也可以得到最小值。

以上方式可以同样用于证明你自己的解法。

Answer 2

left[..]是在仅符合左规则下分的糖果最少的分配方案，且每个人分到的糖果也是最少的。同样的right[...]是在仅符合右规则下分的糖果最少的分配方案，且每个人分到的糖果也是最少的。

或者直接说

left[..]是在仅符合左规则下每个人分到的糖果最少的分配方案。
right[..]是在仅符合右规则下每个人分到的糖果最少的分配方案。
（自然也是分的糖果最少的分配方案）

• 我觉的上面这个结论画图来看还是挺直观的。在严格递增（从左到右或从右到左）的时候从1开始不断地加1，其他的时候为1。应该就是最少的，而且每个人获得也是最少的。

• 当然我们也可以用反证法来证明，

  • 存在一个更优解left2，那么一定存在i,使得left2[i] < left[i]
  • 这里的left[i]一定是大于1的，否则left2[i]就只能是0了，但是每个人必须要有一个糖果。也就说这里的i是处于严格递增中的一点，1->2->3...，left2[i]比left[i]小，那么left2从此段严格递增的起点到i是无法符合左规则的(1->2->3 ok, 1->?->2 no)，与left2是解矛盾。

那么此时问题3用反证法来证明更简单一些了。

• 假设存在一个更优解candy2，那么一定存在一个i,使得candy2[i] < candy[i]，即candy2[i] < max(left[i],right[i])。
• 又因为left[i]是符合左规则写分配的最少糖果数，right[i]是符合右规则下分配的最少糖果数，所以candy[2]一定违法了左右规则中的一个，不是可行解的一部分，与candy是解矛盾。故candy为最优解。