leetcode 135分发糖果

这是一道hard题，不好想，但最后还是想出来了，私以为还是根据一些思想方法自己想出来做法印象比较深刻，其次看人家的做法思想自己写代码，其次看代码理解默写，其次直接抄代码；

首先，给每个孩子都发一个糖果vector<int> res(len,1), 然后调整，

正向调整，如果当前孩子比之前孩子的分数高，那么令当前孩子的糖果数比之前孩子糖果数大1 res[i]=res[i-1]+1；

反向调整，如果当前孩子比之前孩子的分数高，那么比较当前孩子的糖果数和之前孩子的糖果数+1，取更大的为当前孩子糖果数res[i]=max(res[i],res[i+1]+1)；

最后，将每个孩子的糖果数加起来；sum(res.begin(),res.end());

class Solution {

public:

    int candy(vector<int>& ratings) {

        int len=ratings.size();

        vector<int> res(len,);

        for(int i=;i<len;i++){

            if(ratings[i]>ratings[i-]){

                res[i]=res[i-]+;

            }

        }

        for(int i=len-;i>=;i--){

            if(ratings[i]>ratings[i+]){

                res[i]=max(res[i],res[i+]+);

                //cout<<"1"<<endl;

            }

        }

        int sum=;

        for(int n:res){

            sum+=n;

        }

        return sum;

    }

};

巴特西

leetcode 135分发糖果

最新文章

热门文章