题解 | 分糖果问题

class Solution {
public:
    int candy(vector<int>& arr) {
        int n = arr.size();
        vector<int> score (n,0);
        score[0] = 1;
        for(int i =0;i<n-1;i++){
            if(arr[i]<arr[i+1]){
                score[i+1] = score[i]+1;
            }else{
                score[i+1]= 1;
            }
        }
        int result = 0;
        for (int i =0; i<n; i++) {
            result+=score[i];
        }
        return result;
    }
};

这是第一版错误代码,因为每个小孩至少分到一个糖果,所以可以在初始化时将score全部初始化成1,也就不需要else判断了,第二个问题是其只考虑了从左向右单向递增的情况.

一个小孩拿到多少糖果同时和左边得分比其低的人数和右边得分比其低的人数有关