[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]

代码如下：

	public class Solution {
	public int candy(int[] ratings) {
	if (ratings.length == 0)
	return 0;
	int len = ratings.length;
	int[] candy = new int[len];
	candy[0] = 1;
	for (int i = 1; i < len; i++)
	candy[i] = ratings[i] > ratings[i - 1]? candy[i - 1] + 1: 1;
	int sum = candy[len - 1];
	for (int i = len - 2; i >= 0; i--) {
	candy[i] = ratings[i] > ratings[i + 1]? candy[i] >= candy[i + 1] + 1? candy[i]: candy[i + 1] + 1: candy[i];
	sum += candy[i];
	}
	return sum;
	}
	}

view raw candy.java hosted with ❤ by GitHub

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

	class Solution {
	public:
	int candy(vector<int>& ratings) {
	int sum = 1, curr = 1, len = ratings.size(), dLen = 1;
	if(!len)return 0;
	for(int i = 1; i < len; ++i)
	{
	if(ratings[i] < ratings[i - 1])
	{
	sum += --curr;
	dLen++;
	}
	else
	{
	if(dLen > 1)
	{
	sum += (1 - curr) * (curr < 1? dLen: dLen - 1);
	dLen = 1;
	curr = 1;
	}
	if(ratings[i] > ratings[i - 1])sum += ++curr;
	else
	{
	sum++;
	curr = 1;
	dLen = 1;
	}
	}
	}
	if(dLen > 1)sum += (1 - curr) * (curr < 1? dLen: dLen - 1);
	return sum;
	}
	};

view raw candy.cpp hosted with ❤ by GitHub