分配问题_1011
需积分: 0 172 浏览量
2022-08-03
21:18:35
上传
评论
收藏 138KB PDF 举报
2020/12/31 My Notes - LeetCode
https://leetcode.com/notes/ 1/2
. Candy
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
Example 1:
Example 2:
给孩子分配糖果
Greedy, Array
every child must have at least one candy, and more candies than its neighbors with a higher rating
value
1. iterate left to right [1, size), if cur > before , left[i] = left[i-1]+1
2. iterate right to left [size-2, 0], if cur > after , right[i] = right[i+1]+1
3. iterate two candy arrays, sum the max element from two arrays.
4. 只关注增量，如果rating更大则把前一位的糖果数拿过来＋1，最后取两个数组各自最大值得和
. Assign Cookies
Assume you are an awesome parent and want to give your children some cookies. But, you should give each
child at most one cookie.
Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies
Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies
The third child gets 1 candy because it satisfies the above two conditions
评论0