Leetcode基础刷题之PHP解析(135. Candy)


2019-8-29 星期四 开始吧

上一题链接Leetcode基础刷题之PHP解析(134. Gas Station)


fe89c9318a6a7a23cedb1fe92404ccd1.png


题目描述

一个经典的发?问题,一排小朋友,每一个小朋友都有一个权重值,你需要给这些小孩发糖果,首先至少每一个小孩都会分到一个糖果,并且权重大的小朋友糖果会多余相邻小朋友拥有的糖果(也就是至少多一个),求最少需要几个糖果。


题目分析

每一种解法就是,首先每个人手上都至少有一个糖果,相邻意味着左右两边,所以我们可以先出左边遍历到右边对比,只要右边的比左边的大,那么右边的糖果就是左边的加1,然后再从右边历到左边,只要左边的比右边权重大,那么当前位置上的小孩的糖果数就是(取右边的加1和之前左边遍历到右边位置的最大值。),不好理解的话举一个场景。

随便举个例子 比如当前三个小朋友的权重是   10  5 15
从左往右遍历的话糖果数    单位个         1  1  2
从右往左遍历的话糖果数    单位个         2  1  1
最终至少需要糖果                       2+1+2 =5

动态图
683b62ff185baac22b36e79f2960e069.gif

代码实现

    /**
     * @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;
    }


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Golang 中互斥锁与读写锁的简单使用

>> 下一篇: Leetcode基础刷题之PHP解析(137. Single Number II)