描述

有N个小朋友站成一排，每个小朋友都有各自的权重值，现在给小朋友分糖果，原则如下：

1，每个小朋友至少有一个糖果；

2，权重值高的小朋友分到的糖果要大于挨着的小朋友的数量；

一共要至少分配多少个糖果呢？

分析

首先，每个小朋友先分一个糖果，然后设定一个初始值为1的增幅变量inc：

1，从左向右遍历数组，如果a[i]>a[i-1]，则increment[i]赋值为inc，同时inc增加1；若果a[i]<a[i-1]，则inc=1。

2，从右向左遍历数组，如果a[i]>a[i+1]，则increment[i]赋值为inc，同时inc增加1；若果a[i]<a[i-1]，则inc=1。

实现

int candy00(vector<int> &ratings)
{
    const size_t n = ratings.size();
    vector<int> increment(n);
    
    // 从左往右扫描
    for(int i=1, inc=1; i<n; i++) {
        if (ratings[i] > ratings[i-1]) {
            increment[i] = max(inc++, increment[i]);
        } else {
            inc = 1;
        }
    }
    
    // 从右往左扫描
    for (int i=n-2, inc=1; i>=1; i--) {
        if (ratings[i] > ratings[i+1]) {
            increment[i] = max(inc++, increment[i]);
        } else {
            inc = 1;
        }
    }
    
    return accumulate(&increment[0], &increment[0]+n, n);
}