[LeetCode]Candy

题目链接

也是当前的值取决于两边的问题，跟Trapping Rain Water是类似的。注意这里题目没有说相等的话该怎么办，这里相等的话并没有分的糖也要相等的设置，所以我们按可以把总糖数降低就可以。我们首先从左往右遍历一次，如果分数大于前一个的话，arr当前位置就赋值为前一个加1，如果小于或者等于就赋值为1。然后从右向左在调整，我们只要调整递减序列，一般递增的时候调整成后面一个加一就可以，不过调整的时候要注意峰值的时候有特殊情况，比如：

• 1，2，3，4，2，1的时候，我们从右向左扫扫到4的时候不应该调整他的值为3，因为还有左边的限制
• 1，2，3，4，3，2，1的时候，如果3，4，3，2，1的权值是递减的话，我们要把3调整成5

所以我们调整的时候，取得是两边限制的最大值，这样才能满足条件。非递减序列不需要调整，DP方程：

• 从左向右时
• if ratings[i] > ratings[i - 1], f[i] = f[i - 1] + 1;
• else, f[i] = 1;
• 从右向左时
• if ratings[i] > ratings[i + 1], f[i] = max(f[i + 1] + 1, f[i]);
• else, f[i] = f[i]

代码如下：

另一方面，也有constant space and one pass的做法，很显然，对于处在谷底的元素我们只需要分配一颗糖，对于处在波峰的元素我们分配由左右序列推定的较大值。那么如此一来，在从左向右扫的时候，对于递增序列，我们只需要分配比前一个值多一个candy即可。对于恒定序列，除了两端，其他所有给一个candy即可。对于递减序列，我们依次分配比前一个值少一个candy，当我们到达谷底时，若当前分配candy不为1，代表我们需要对递减序列的值进行修正，那么只需要对递减序列加上或者减去对应的值即可。可以维护一个变量记录递减序列的长度，对于递减序列最左边的值n，视情况而定，可能需要修正，可能不需要，因为其值还取决于它左边的序列，当遍历到谷底的candy值小于1，代表我们要对所有序列值加上一个数k，那么对于n来说，自然要取右边较大的值。但是如果遍历到谷底的candy值大于1，代表我们要对序列上的所有值减去一个数k，那么此时我们不需要修正n，因为其值取决于其左边序列所推定的较大值。
代码如下：