一次遍历，常数空间

将ratings大小看成一个个山峰，v1v2为两侧谷底 top为峰顶
峰值的个数由左右两个斜坡中较长的决定

C++ 代码

class Solution {
public:
    int candy(vector<int>& ratings) {
        if(ratings.empty()) return 0;
        int n = ratings.size();
        int v1 = 0, top = 0, v2 = 0;
        int res = 0;

        while(v1 < n){
            //找出由v1 top v2构成的山峰，top为峰顶
            top = v1;
            while(top + 1 < n && ratings[top + 1] > ratings[top]) top++;

            v2 = top;
            while(v2 + 1 < n && ratings[v2 + 1] < ratings[v2]) v2++;

            //按等差数列公式进行计算
            //v1到top的上升坡较长时，峰顶算在上升坡中
            if(top - v1 >= v2 - top){
                res += (1 + (1 + top - v1)) * (top - v1 + 1)/2; //上升坡糖果数1,2,...,1+top-v1个
                res += (1 + (v2 - top)) * (v2 - top)/2; //下降坡糖果数1,2,..., v2-top个
            }
            else{
                res += (1 + (top - v1 )) * (top - v1)/2;
                res += (1 + (1 + v2 - top)) * (v2 - top + 1)/2;
            }

            //如果v1==v2说明当前山是单个点，右移进行之后的计算，也避免了再次使v1=v2导致的无限循环
            if(v1 == v2) 
                v1 = v2 + 1;
            else {
                v1 = v2;    //v2是当前山的右谷底，也是下个山的左谷底
                res--;      //因为下次要作为左谷底再算，所以将v2处的一个糖果去掉
            }

        }
        return res;
    }
};