题解 | #分糖果问题#

class Solution {
public:
    int candy(vector<int>& arr) {
        //记录每个位置的糖果数，初始为1
        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 = nums[arr.size() - 1]; 
        //从右到左遍历
        for(int i = arr.size() - 2; i >= 0; i--){ 
            //如果左边更大但是糖果数更小
            if(arr[i] > arr[i + 1] && nums[i] <= nums[i + 1]) 
                nums[i] = nums[i + 1] + 1; 
            //累加和
            res += nums[i]; 
        }
        return res;
    }
};

// 思路感觉没错呀，错了错了，因为最小值可能有多个，而且这多个的最小值可能分布在不同相邻下标
// 所以不能用以下解法
// #include <numeric>
// #include <vector>
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      * pick candy
//      * @param arr int整型vector the array
//      * @return int整型
//      */
//     int candy(vector<int>& arr) {
//         // write code here
//         // 找到arr中的最小值位置
//         int index = min_element(arr.begin(),arr.end())-arr.begin();
        
//         int left = index-1, right = index+1;

//         vector<int> temp(arr.size(),1);

//         while(left>=0)
//         {
//             if(arr[left]==arr[left+1])
//                 temp[left] = temp[left+1];
//             else if(arr[left]>arr[left+1])
//                 temp[left] = temp[left+1]+1;
//             else
//                 temp[left] = temp[left+1]-1;

//             --left;
//         }

//         while(right<arr.size())
//         {
//             if(arr[right]==arr[right-1])
//                 temp[right] = temp[right-1];
//             else if(arr[right]>arr[right-1])
//                 temp[right] = temp[right-1]+1;
//             else
//                 temp[right] = temp[right-1]-1;

//             ++right;
//         }

//         int ans = accumulate(temp.begin(), temp.end(), 0);
        
//         return ans;
//     }
// };