Leetcode基础刷题之PHP解析(135. Candy）
2019-8-29 星期四 开始吧
上一题链接Leetcode基础刷题之PHP解析(134. Gas Station）
题目描述
一个经典的发?问题，一排小朋友，每一个小朋友都有一个权重值，你需要给这些小孩发糖果，首先至少每一个小孩都会分到一个糖果，并且权重大的小朋友糖果会多余相邻小朋友拥有的糖果(也就是至少多一个)，求最少需要几个糖果。
题目分析
每一种解法就是，首先每个人手上都至少有一个糖果，相邻意味着左右两边，所以我们可以先出左边遍历到右边对比，只要右边的比左边的大，那么右边的糖果就是左边的加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; }
无评论