LeetCode 135. Candy

太过爱你忘了你带给我的痛 2024-04-18 23:45 68阅读 0赞

题目描述：

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

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

*  每个孩子至少分配到 1 个糖果。
 *  相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

分析：

分析一下，乍一看好像这个小朋友的糖果之和他旁边的小朋友有关，但是思考一下好像也不大对，旁边的小朋友又会受旁边的旁边影响。

我们把能想到的情况列出来：

*  左边的小朋友分数 < 当前小朋友分数, 当前小朋友分数 = 左边的小朋友分数 + 1
 *  左边的小朋友分数 > 当前小朋友分数, 当前小朋友分数=1, 左边如果呈递减的趋势，那么递减的序列对应加1(还有特殊情况)

*  峰值的点的取值很重要
 *  比如1 5 4, 4位当前节点，5为峰值，设置为1，前面5不需要(5已经加过了【不包含峰值】)
 *  比如1 5 4 3 2, 2位当前节点，5为峰值，设置为1，前面5 4 3全部加一
 *  比如1 2 3 5 4 3 2 1, 1位当前节点，5为峰值，设置为1，前面4 3 2全部加一(5需要设置为两边最高值加一)
 *  比如1 4 4 3 2, 2位当前节点，5为峰值，设置为1，前面4 3全部加一(峰值指向后面那个4【包含峰值】)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1][]

代码：

class Solution {
    public:
        int candy(vector<int>& ratings) {
            //每个小宝贝至少有一颗糖，相邻小伙伴分数高要获得更多的糖果
            //记录峰值，比如1 5 4 3 2，topIndex指向5
            //记录峰值，比如1 4 4 3 2，topIndex指向第二个4
            int topIndex = 0;
            //记录峰值下标对应小宝贝的糖果数
            int topIndexValue = 1;
            int len = ratings.size();
            //下界
            if(len == 0) return 0;
            //长度不等于0，那么第一个小朋友初始肯定设置为1
            int result = 1;
            //记录左侧小朋友多少颗糖,最开始那个是1颗糖
            int leftValue = 1;
            for(int i = 1; i < len; i++){
                //和左侧判断
                if(ratings[i] >= ratings[i-1]) {
                    if(ratings[i] > ratings[i-1]){
                        result += (leftValue + 1);
                        //刷新
                        leftValue = leftValue + 1;
                    } 
                    else{
                        result += 1;   //等于情况
                        leftValue = 1;
                    } 
                    //刷新峰值
                    topIndex = i;
                    topIndexValue = leftValue;
                }else{
                    //左边的小朋友分数 > 当前小朋友分数, 当前小朋友分数=1, 左边如果呈递减的趋势，那么递减的序列对应加1
                    //峰值的点的取值很重要
                    //比如1 5 4, 4位当前节点，设置为1，前面5不需要(5已经加过了【不包含峰值】)
                    //比如1 5 4 3 2, 2位当前节点，设置为1，前面5 4 3全部加一
                    //比如1 2 3 5 4 3 2 1, 1位当前节点，设置为1，前面4 3 2全部加一(5需要设置为两边最高值加一)
                    //比如1 4 4 3 2, 2位当前节点，设置为1，前面4 3全部加一(峰值指向后面那个4【包含峰值】)
                    //判断峰值和前一个对等还是大于
                    if(topIndex > 0){
                        if(ratings[topIndex] == ratings[topIndex-1]) result += (i - topIndex + 1);
                        else {
                            //山峰形状
                            //首先除了峰值那个点全部+1
                            result += (i - (topIndex + 1) + 1);
                            //然后对峰值点判断
                            result = topIndexValue >= (1 + i - topIndex) ? result : result + (1 + i - topIndex - topIndexValue);
                            //更新峰值
                            topIndexValue = max(topIndexValue, (1 + i - topIndex));
                        }
                    }
                    else result += (i - topIndex + 1);   //峰值为第一个,左边没有
                    //刷新
                    leftValue = 1;
                }
            }
            return result;
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/372b5403becb42d49b7d9687d12d54ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/04603c5df3ab4709a619c92de238655d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/35daa624ebef40f4b1563205f9399ef4.png