Leetcode 135. 分发糖果（问题分解）

本文主要是介绍Leetcode 135. 分发糖果（问题分解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 135. 分发糖果

根据描述，可知更多糖果发生在相邻两个孩子的rating更高者中，对于一个孩子来说，左右两侧都视为相邻，即ratings[ i ] > ratings[ i-1 ] 或 ratings[ i ] > ratings[ i+1 ]都会令糖果增加

由此则将问题分解成两个方面，分别考虑ratings大于左侧和ratings大于右侧两种情况
使用nums[ ] 记录每个孩子的糖果数，这个数组初始化为1

从左向右考虑ratings大于左侧，即ratings[ i ] > ratings[ i-1 ]情况，此时令 i 处的糖果数nums[ i ]直接赋值为nums[ i-1 ] + 1即可满足条件

接下来从右向左考虑ratings大于右侧情况，即ratings[ i ] > ratings[ i+1 ]情况
注意的是，此时nums并非全1的初始化状态，而是已经计算过的数组，若ratings[ i ] > ratings[ i+1 ]发生，而此时nums[ i ] > nums[ i+1 ]已经满足，则无需再次分配糖果，否则同理左遍历为nums[ i ]赋值

如ratings{5，10，7}，左遍历后nums{1，2，1}，此时进行右遍历则无需为nums[ 1 ]分配更多糖果

class Solution {public int candy(int[] ratings) {int n = ratings.length;int nums[] = new int [n];Arrays.fill(nums, 1);for(int i = 1; i < n; i ++){if(ratings[i] > ratings[i-1])nums[i] = nums[i-1] + 1;}for(int i = n-2; i >= 0; i --){// 特判if(ratings[i] > ratings[i+1] && nums[i] <= nums[i+1])nums[i] = nums[i+1] + 1;}int sum = 0;for(int i : nums){sum += i;}return sum;}
}

这篇关于Leetcode 135. 分发糖果（问题分解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---