文章目录
问题描述问题解析代码实现
问题描述
问题解析
前向遍历糖果数组,则相邻的孩子中,分高且位于后面的孩子必定能分到较多的糖果; 后向遍历糖果数组,则相邻的孩子中,分高且位于前面的孩子必定能分到较多的糖果。
代码实现
class Solution {
public:
int candy(vector
<int>& ratings
) {
int res
=0, n
=ratings
.size();
vector
<int>nums(n
,1);
for(int i
=0;i
<n
-1;++i
){
if(ratings
[i
+1]>ratings
[i
]){
nums
[i
+1]=nums
[i
]+1;
}
}
for(int i
=n
-1;i
>0;--i
){
if(ratings
[i
-1]>ratings
[i
]){
nums
[i
-1]=max(nums
[i
-1], nums
[i
]+1);
}
}
for(int num
:nums
){
res
+=num
;
}
return res
;
}
};
转载请注明原文地址: https://mac.8miu.com/read-500251.html