leetcode 135 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?

一句话题意

最少糖果问题。一排小孩,每个孩子有一个优先级,每个孩子至少要发给一个糖果,优先级高的比周围的孩子的糖果要多。

解题思路

初始化,肯定每人一糖。

为了保证优先级大的比相邻的且优先级小的要糖果多。所以我们分两次处理,一次处理比左边的优先级低的多,一次处理兼顾左边的多的情况下比右边的优先级低的多。

那么第一次从左到右,if (r[i] >r[i-1]) 那么c[i] = c[i-1]+1;    c为糖果数组,r为优先级

从右边到左边扫时,需要注意的要保证之前的不能减少,也就是变大的才要改,即

if(r[i] > r[i+1]) c[i] = max(c[i], c[i+1]+1)

分类: LeetCode算法设计

0 条评论

发表评论