题目主要信息:

  • 给定一个数组,每个元素代表孩子的得分,每个孩子至少分得一个糖果
  • 相邻两个位置得分高的要比得分低的分得多,得分相同没有限制
  • 求最少总共需要多少糖果数

具体思路:

要想分出最少的糖果,利用贪心思想,肯定是相邻位置没有增加的情况下大家都分到1,相邻位置有增加的情况下,分到糖果数加1就好。什么情况下会增加糖果,相邻位置有得分差异,可能是递增可能是递减,如果是递增的话,糖果依次加1,如果是递减糖果依次减1?这不符合最小,必须从1开始加才是最小,那我们可以反向加1.

  • step 1:使用一个辅助数组记录每个位置的孩子分到的糖果,全部初始化为1.
  • step 2:从左到右遍历数组,如果右边元素比相邻左边元素大,意味着在递增,糖果数就是前一个加1,否则保持1不变。
  • step 3:从右到左遍历数组,如果左边元素比相邻右边元素大, 意味着在原数组中是递减部分,如果左边在上一轮中分到的糖果数更小,则更新为右边的糖果数+1,否则保持不变。
  • step 4:将辅助数组中的元素累加求和。

具体过程可以参考如下图示: alt

代码实现:

class Solution {
public:
    int candy(vector<int>& arr) {
        vector<int> nums(arr.size(), 1); //记录每个位置的糖果数,初始为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;
    }
};

复杂度分析:

  • 时间复杂度:O(n)O(n),单独遍历两次
  • 空间复杂度:O(n)O(n),记录每个位置糖果数的辅助数组