题解 | #分糖果问题#

这一道题其实蛮有趣的，都说是贪心，我没感觉出来。所以我做得比较复杂。这道题时间复杂度要求较高，但是空间复杂度为O(n),所以从这里出发我定义了left和right两个vector来获取左右大小情况（注意前后先插入头尾两个数），然后从左遍历一次，再从右遍历一次即可满足要求了。cr和cl这两个参数主要是用来观察是否有连续右边的数大或者连续左边的数大。

public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        // write code here
        int res = 0;
        int size = arr.size();
        if(size==1)
            return 1;
        vector<int> left(size,0);
        vector<int> right(size,0);
        vector<int> rest(size,1);
        arr.push_back(arr[size-1]);
        arr.insert(arr.begin(),arr[0]);
        for(int i =1.;i<arr.size()-1;i++)
        {
            left[i-1] = arr[i]-arr[i-1];
            right[i-1] = arr[i]-arr[i+1];
        }
        int cl = 0;
        for(int i=0;i<rest.size();i++)
        {
            if(left[i]>0&&cl==0)
            {
                rest[i]++;
                cl = 1;
            }
            if(left[i]>0&&cl==1)
            {
                rest[i] = rest[i-1]+1;
                cl = 1;
            }
            if(left[i]<=0)
                cl = 0;
        }
        for(int i=0;i<rest.size();i++)
            cout<<rest[i]<<" ";
        cout<<endl;
        int cr = 0;
        for(int i=rest.size()-1;i>=0;i--)
        {
            if(right[i]>0&&cr==0)
            {
                if(rest[i]<=rest[i+1])
                    rest[i]++;
                cr = 1;
            }
            if(right[i]>0&&cr==1)
            {
                if(rest[i]<=rest[i+1])
                    rest[i] = rest[i+1]+1;
                cr = 1;
            }
            if(right[i]<=0)
                cr = 0;
        }  
        int out = 0;
        for(int i=0;i<rest.size();i++)
            out+=rest[i];
        
        return out;
    }
};