LeetCode 135 Candy

题目链接:Candy

题意:N个孩子排成一排,每个孩子有个rating值,现在给每个孩子发糖果,要求:

  • 每人至少一个
  • rating值比相邻孩子高的人得的糖果数要比相邻的多

求糖果总数最少是多少?

 

贪心,每人尽量发最少的糖。

\(L_i\) 表示第i个数左边相邻非递减区间去重后的长度

\(R_i\) 表示第i个数右边相邻非递增区间去重后的长度

那么第i个孩子得到的糖果数为 \(max(L_i,R_i)\)

时间复杂度 \(O(n)\)

 

 

 

Categories: LeetCode