135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

• n == ratings.length
• 1 <= n <= 2 * 104
• 0 <= ratings[i] <= 2 * 104

 

int candy(vector<int>& ratings) {

vector<int>sortVec = ratings;

    set<int>tmpSet;

    for (auto it : sortVec)

    {

        tmpSet.insert(it);

    }

    sortVec.clear();

    for (auto it : tmpSet)

    {

        sortVec.push_back(it);

    }

    sort(sortVec.begin(), sortVec.end());

    map<int, vector<int>>mapIndex;

    for (int i = 0; i<ratings.size(); i++)

    {

        mapIndex[ratings[i]].push_back(i);

    }

    vector<int>ret(ratings.size(), -1);

    //从评分低开始

    for (int i = 0; i<sortVec.size(); i++)

    {

        vector<int>indexVec = mapIndex[sortVec[i]];

        for (int j = 0; j<indexVec.size(); j++)

        {

            //已计算过

            if (ret[indexVec[j]] != -1)

            {

 

                //处理左右两边

                int tmp = 1;

                //判断左边

                if (indexVec[j] - 1 >= 0 )

                {

                    //未计算过

                    if (ret[indexVec[j] - 1] == -1)

                    {

                        ///和前一个不相等

                        if (ratings[indexVec[j] - 1] != ratings[indexVec[j]])

                        {

                            tmp = ret[indexVec[j]] + 1;

                        }

                        ret[indexVec[j] - 1] = tmp;

                        tmp = 1;

                    }  

                }

                //判断右边

                if (indexVec[j] + 1 < ratings.size())

                {

                    //已计算过

                    if (ret[indexVec[j] + 1] != -1)

                    {

                        continue;

                    }

                    ///和前一个不相等

                    if (ratings[indexVec[j] + 1] != ratings[indexVec[j]])

                    {

                        tmp = ret[indexVec[j]] + 1;

                    }

                    ret[indexVec[j] + 1] = tmp;

                }

                continue;

            }

            //处理左右两边

            int tmp = 1;

            ret[indexVec[j]] = tmp;

            //判断左边

            if (indexVec[j] - 1 >= 0)

            {

                //已计算过

                if (ret[indexVec[j] - 1] != -1)

                {

                    continue;

                }

                ///和前一个不相等

                if (ratings[indexVec[j] - 1] != ratings[indexVec[j]])

                {

                    tmp = ret[indexVec[j]] + 1;

                }

   

                ret[indexVec[j] - 1] = tmp;

                tmp = 1;

            }

            //判断右边

            if (indexVec[j] + 1 < ratings.size() )

            {

                //已计算过

                if (ret[indexVec[j] + 1] != -1)

                {

                    continue;

                }

                ///和前一个不相等

                if (ratings[indexVec[j] + 1] != ratings[indexVec[j]])

                {

                    tmp = ret[indexVec[j]] + 1;

                }

                ret[indexVec[j] + 1] = tmp;

            }

        }

    }

    for (int i = 0; i < ret.size(); i++)

    {

        if (i - 1 > 0 && ratings[i] > ratings[i - 1] && ret[i] <= ret[i - 1])

        {

            ret[i] = ret[i - 1] + 1;

        }

        if (i +1 < ratings.size() && ratings[i] > ratings[i + 1] && ret[i] <= ret[i + 1])

        {

            ret[i] = ret[i + 1] + 1;

        }

    }

    int socre = 0;

    for (auto it : ret)

    {

        socre += it;

    }

    return socre;

    }