https://oj.leetcode.com/problems/candy/
一排小孩,每个有自己的ratings,每个小孩至少一个candy,并且ratings号大于neighbour的小孩的candy数大于neighbour的。
先初始化每个小孩一个candy
从左到右扫描一遍,如果右边的 ratings数大于左边,则右边candy数为左边 +1
从右到做扫面一遍,如果左边的 ratings数大于右边,则左边candy数为 右边+1,或者为它本身。
比如 a b c d 四个位置,从左到右,保证了如果右边大,则右边的candy大。比如如果c比b大,则c的值更大。
第二遍时候,处理左边,因为b比c小,所以在这趟中b的值是不会变的,c的值有可能变,但无论怎么变,也是往大了变,所以,c相对于b的candy值,依然是大。
在老钱的启发下才做出来,自己想的那个方法太麻烦了,还超时。。。。
class Solution { public: int candy(vector<int> &ratings) { int len = ratings.size(); if(len == 1) return 1; int ans = 0; vector<int> candy(len,1); for(int i = 1;i<len;i++) { if(ratings[i]>ratings[i-1]) candy[i] = candy[i-1] + 1; } for(int i = len -2 ;i>=0;i--) { if(ratings[i]>ratings[i+1]) candy[i] = candy[i]>candy[i+1]?candy[i]:candy[i+1]+1; } for(int i = 0;i<len;i++) ans += candy[i]; return ans; } };