算法 - 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 的情况也可以得到最小值。

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