分发糖果
核心思想是两边遍历，正遍历一次和反遍历一次
单项遍历写了一天过33个测试
贪心算法
class Solution { public: int candy(vector<int>& ratings) { int sum=0 ; vector<int> num(ratings.size(),1); for(int i=0 ; i < ratings.size()-1 ;i++ ) //正向，发现分高的孩子多给一个糖 { if(ratings[i+1] > ratings[i]) num[i+1] = num[i]+1; } for(int i= ratings.size()-1 ; i >=1 ;i-- )//反向，发现分高的孩子多给一个糖 { if(ratings[i] < ratings[i-1]) num[i-1] = max(num[i]+1 , num[i-1]) ;// 找最大的 } for(auto it:num) sum += it; return sum; } };
二刷
class Solution { public: int candy(vector<int>& ratings) { int result=0; vector<int> nums(ratings.size(),1); for(int i=0 ; i<ratings.size()-1 ; i++) { if(ratings[i] < ratings[i+1]) { nums[i+1] = nums[i] + 1; } } for(int i = ratings.size()-1 ; i>0 ;i--) { if(ratings[i] < ratings[i-1] ) { nums[i-1] = max(nums[i-1], nums[i]+1); } } for(auto it:nums) result += it; return result; } };
