题解 | 分糖果问题

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        // write code here
        //我的思路是找到每个下降的区间 倒推回来第一个开始下降的需要多少 才能够让最后一个人至少一个糖果。
        //找到递减区间。
        int size=arr.size();
        if(size==1)return 1;
        vector<int> candynum(size,0);
        candynum[0]=1;
        for(int i=1;i<size;i++){
            if(arr[i]<arr[i-1]){
                int left=i-1;
                while(arr[i]<arr[i-1]&&i<size){
                    i++;
                }
                //int descentsize=i-left;
                i--;
                int count=1;
                for(int j=i;j>left;j--){//不能大于left 因为left已经被赋值 且值可能较大 比如123456 54 6的值就相对较小
                //注意 但是也有可能是 18 65432 这样8拿的少。
                    candynum[j]=count;
                    count++;
                }
                if(candynum[left]<count)candynum[left]=count;
            }
            else if(arr[i]>arr[i-1]){
                candynum[i]=candynum[i-1]+1;
            }
            else candynum[i]=1;//这里 不对。
            //如 123456 621 (若相同则无此限制，则第二个6拿的应该较少
        }
        int res=0;
        for(int i=0;i<size;i++){
            res+=candynum[i];
        }
        return res;
    }
  /*
  下面是官解。就是保证每个人至少一个 所以初始化=1；保证若两边的比自己大 则两边的糖果数量+1
  第一趟 保证 右大于左，保证了右边比自己大的元素数量比自己多。
  第二趟 保证 如果左边比自己大，则左边的元素至少比自己多。
  举例 1 12 6 3 2 7
   int candy(vector<int>& arr) {
        // write code here
        vector<int> nums(arr.size(),1);
        for(int i=1;i<arr.size();i++){
            if(arr[i]>arr[i-1])nums[i]=nums[i-1]+1;
        }
        int res=0;
        for(int i=arr.size()-1;i>0;i--){
            if(arr[i-1]>arr[i]&&nums[i-1]<=nums[i])nums[i-1]=nums[i]+1;
            res+=nums[i];
        }
        res+=nums[0];
        return res;
    }
  */
};