2019-08-29 吴亲库里 库里的深夜食堂
一个经典的发🍬问题，一排小朋友，每一个小朋友都有一个权重值，你需要给这些小孩发糖果，首先至少每一个小孩都会分到一个糖果，并且权重大的小朋友糖果会多余相邻小朋友拥有的糖果(也就是至少多一个)，求最少需要几个糖果
每一种解法就是，首先每个人手上都至少有一个糖果，相邻意味着左右两边，所以我们可以先出左边遍历到右边对比，只要右边的比左边的大，那么右边的糖果就是左边的加1，然后再从右边历到左边，只要左边的比右边权重大，那么当前位置上的小孩的糖果数就是（取右边的加1和之前左边遍历到右边位置的最大值。),不好理解的话举一个场景。
随便举个例子 比如当前三个小朋友的权重是 10 5 15
从左往右遍历的话糖果数 单位个 1 1 2
从右往左遍历的话糖果数 单位个 2 1 1
最终至少需要糖果 2+1+2 =5
/**
* @param Integer[] $ratings
* @return Integer
*/
function candy($ratings) {
$sum=0;
for($i=0;$i<count($ratings);$i++){
$nums[$i]=1;
}
for($i=0;$i<count($ratings);$i++){
if($ratings[$i+1]>$ratings[$i]){
$nums[$i+1]=$nums[$i]+1;
}
}
for($i=count($ratings)-1;$i>=0;$i--){
if($ratings[$i-1]>$ratings[$i]){
$nums[$i-1]=max($nums[$i-1],$nums[$i]+1);
}
}
for($i=0;$i<count($nums);$i++){
$sum +=$nums[$i];
}
return $sum;
}
