题解 | #分糖果问题#

class Solution {
public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        // write code here
        int res = 0;
        vector<int> num(arr.size(), 0);
        for(int i = 0; i < arr.size(); i++) {
            // 初始第一个人分一个糖果
            if(i == 0) 
                num[i] = 1;
            // 如果当前的人得分比前一个多，就给当前人多分一个糖果
            else if(arr[i] > arr[i-1]) {
                num[i] = num[i - 1] + 1;
            }
            // 如果当前人的得分小于等于前一个，则给当前人分一个糖果
            else if(arr[i] <= arr[i-1]) {
                num[i] = 1;
                // 当前人的得分等于前一个，直接跳过
                if(arr[i-1] == arr[i])
                    continue;
                int j = i;
                // 当前人的得分小于前一个，需要考虑前一个人的糖果数是不是大于当前人
                // 循环遍历
                while(j >= 1) {
                    // 如果前一个人的糖果数大于当前或者前一个人的得分小于等于当前人，不需要给前一个人多分糖果
//                     if( num[j-1] > num[j] || arr[j-1] <= arr[j])
//                         break;
                    // 只有前一个人的糖果数等于当前人同时前一个人得分大于当前人时，将前一个人的糖果数加一
                    if(num[j-1] == num[j] && arr[j-1] > arr[j])
                        num[j-1]++;
                    else
                        break;
                    j--;
                }
            }
        }
        for(auto x : num)
            res += x;
        return res;
    }
};