首页 > 代码库 > Leetcode - candy

Leetcode - candy

被第二个条件给坑了

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.
条件二言下之意是如果两个相邻小孩的rating一样,那么它们的candy谁多谁少无所谓。

所以思路是从左遍历到右,再从右遍历到左,记录每个值左右方向的严格递增子序列的长度(如果没有形成严格递增序列,那么长度为0)。所以小孩i 应该得到糖果数量等于相应左(右)严格递增子序列的较大值+1。复杂度O(n)。


  有兴趣可以思考下如果再增加一个条件的其他解法,

   3: Children with the same rating should get the same candies with their neighbors.


class Solution {
public:
	int candy(vector<int> &ratings) {

		vector<int> l2rMax((int)ratings.size(), 0);
		vector<int> r2lMax((int)ratings.size(), 0);

		
		for (int i = 1; i < ratings.size(); i++)
		{
			if (ratings[i] > ratings[i - 1])
				l2rMax[i] = l2rMax[i - 1] + 1;
		}

		for (int i = ratings.size() - 2; i >= 0; i--)
		{
			if (ratings[i] > ratings[i + 1])
				r2lMax[i] = r2lMax[i + 1] + 1;
		}

		int sum = 0;
		for (int i = 0; i < ratings.size(); i++)
		{
			sum += 1;
			sum += (r2lMax[i] > l2rMax[i] ? r2lMax[i] : l2rMax[i]);
		}

		return sum;
	}
};


Leetcode - candy