leetcode糖果问题，这种做法为什么可行?-灵析社区

leetcode糖果问题，这种做法为什么可行? [leetcode糖果问题](https://link.segmentfault.com/?enc=qmaNQWeOe4%2BDCx2tFqGVhw%3D%3D.ocar3CDjNlgV9MLKyPLyELfql2evkFnhSBEaDMvUiLTBso5mdCnGVDVc%2FP28TvnuOEv5a7AceMcp%2BQs3ZMnERpiHuJmRz5qSw63E9%2BedWPCsaPOatMVNGl0vY2ecVe%2FPhkXcR%2Bfwqi0naBCxICYhLDjqJOMhWCmnT65lVxMN%2FpOxPQWmM%2BR8e4dz2vTpSXHu) 这个官方题解并没有证明，只是说了一下过程。我有以下几点疑问： * `left[..]`是在仅符合左规则下分的糖果最少的分配方案吗？同样的`right[...]`是在仅符合右规则下分的糖果最少的分配方案吗？ * 为什么取仅符合左规则的值和仅符合右规则的值的最大值可以同时符合左右规则呢? * 就算符合左右规则，为什么这种方案下分的糖果是最少的呢?  var candy = function(ratings) { const n = ratings.length; const left = new Array(n).fill(0); for (let i = 0; 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 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] 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 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] pre + cur); }