题解 | 分糖果问题

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        // write code here
        int n=arr.size();
        if(n==0)
        {
            return 0;
        }
        vector<int> candy(n,1);//默认每个孩子一颗
        //从左到右遍历
        for(int i=1;i<n;i++)
        {
            if(arr[i]>arr[i-1])
            {
                candy[i]=candy[i-1]+1;//保证右比当前得分多的要多拿一颗
            }
        }

        //从右往左遍历，左比当前得分多的要多拿一颗
        for(int i=n-2;i>=0;i--)
        {
             if(arr[i]>arr[i+1])
             {
                //左比右大，因为已经从左到右遍历了，所以当前值的右边一定是满足的，左边同时对于它的左边也是满足的
                //所以既要确保左边满足其右边，也满足其左边，所以要取已经满足左边的糖果数和满足右边的最小糖果数之间的
                //最大值
                candy[i]=max(candy[i],candy[i+1]+1);
             }
        }
        int res=0;
        for(int i:candy)
        {
            res+=i;
        }
        return res;
    }
};