首页 > 代码库 > Candy
Candy
Candy
There are N children standing in a line. Each child is assigned a rating value.
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.
What is the minimum candies you must give?
分析: 主要问题是可以从左升序或者从右升序，如何取大值。
方法一：从左从右分别计算一次，对值校正。并计算出最大值。要保存中间初步的值，空间复杂度:O(n)
class Solution {public: int candy(vector<int> &ratings) { int n = ratings.size(); if(n == 0) return 0; int totalCandy = 0; int *getCandy = new int[n]; getCandy[0] = 1; for(int i = 1; i < n; ++i) if(ratings[i] > ratings[i-1]) getCandy[i] = getCandy[i-1] + 1; else getCandy[i] = 1; totalCandy += getCandy[n-1]; for(int i = n-1; i > 0; --i) { if(ratings[i-1] > ratings[i]) getCandy[i-1] = max(getCandy[i-1], getCandy[i]+1); totalCandy += getCandy[i-1]; } delete[] getCandy; return totalCandy; }};方法二：从一个方向（此题从左），设置两个变量，通过计算升序长度，降序长度确定精确值。空间复杂度:O(1)
class Solution {public: int candy(vector<int> &ratings) { int LA = 0, LD = 0; // 利用降序长度和升序长度，来求结果。 bool decend = false; int totalCandy = ratings.size(); for(int i = 1; i < ratings.size(); ++i) { if(ratings[i-1] < ratings[i]) { if(LA == 0 || decend == true) LA = 2;//考虑情况：之前为降序，重新设置升序长度 else ++LA; LD = 0; decend = false; //升序时不需要知道之前降序长度。 totalCandy += (LA - 1); }else if(ratings[i-1] > ratings[i]) { decend = true; if(LD == 0) LD = 2; else ++LD; if(LD <= LA) totalCandy += (LD - 2); else totalCandy += (LD - 1); }else { LA = LD = 0; // 出现相同字符，则从第二个重复字符重新开始 } } return totalCandy; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。