首页 > 代码库 > Leetcode#135 Candy
Leetcode#135 Candy
原题地址
遍历所有小孩的分数
1. 若小孩的分数递增，分给小孩的糖果依次+1
2. 若小孩的分数递减，分给小孩的糖果依次-1
3. 若小孩的分数相等，分给小孩的糖果设为1
当递减序列结束时，如果少分了糖果，就补上，如果多分了糖果，就减掉
究竟补多少或减多少，这很容易计算，不啰嗦了。
时间复杂度：O(n)
代码：
1 int candy(vector<int> &ratings) { 2 int n = ratings.size(); 3 int sum = 1; 4 int len = 0; 5 int prev = 1; 6 7 for (int i = 1; i < n; i++) { 8 if (ratings[i] == ratings[i - 1]) { 9 prev = 1;10 len = 0;11 sum += prev;12 }13 else if (ratings[i] > ratings[i - 1]) {14 prev++;15 len = 0;16 sum += prev;17 }18 else if (ratings[i] < ratings[i - 1]) {19 prev--;20 len++;21 sum += prev;22 if (i == n - 1 || ratings[i] <= ratings[i + 1]) {23 sum += prev < 1 ? (1 - prev) * (len + 1) : (1 - prev) * len;24 prev = 1;25 }26 }27 }28 29 return sum;30 }
Leetcode#135 Candy
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。