首页 > 代码库 > Leetcode Candy

Leetcode 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?

题目的意思:

  有N个孩子站成一条线,每个孩子分配一个排名。你将要给这些孩子一些糖果,要求:

  • 每个孩子必须至少有一个糖果
  • 孩子如果有个高排名,将得到糖果比其邻居的多

解题思路是:

  (1)由于每个小孩至少有一个糖果,故将每个小孩的初始糖果初始化为1

  (2)从前往后扫描,如果第i个小孩排名比第i-1高,那么第i个小孩的糖果数目+1

  (3)从后往前扫描,如果第i个小孩排名比第i+1高,那么第i个小孩的糖果数目=max(第i个小孩的糖果数目,第i+1个小孩的糖果数目+1)

  (4)最后将所有小孩的糖果数目累积即可

class Solution {public:    int candy(vector<int> &ratings) {        vector<int> candy(ratings.size(),1);        for(int i = 1; i < ratings.size(); ++ i){            if(ratings[i]>ratings[i-1]) candy[i]=candy[i-1]+1;        }        for(int i = ratings.size()-2; i>=0; -- i){            if(ratings[i] > ratings[i+1]) candy[i] = max(candy[i+1]+1,candy[i]);        }        return accumulate(candy.begin(),candy.end(),0);    }};

 

关于此题目类似的题目

  在一维数组中,找出一个点,使得其所有左边的数字均小于等于它,所有右边的数字都大于等于它。要求在线性时间内返回这个点所在的下标。

如A={1,0,1,0,1,2,3},返回下标4或5

解题思路与上面类似

  首先,从左到右扫描一遍数组,通过一个辅助布尔数组记录哪些大于等于其之前所有元素的元素;

  其次,从右到左扫描一遍数组,如果其后所有元素大于等于当前元素,而且在第一个遍历时当前元素大于等于之前的所有元素,则程序返回下标;

 

int getMagnitutePole(vector<int> A){    if(A.size() == 0) return 0;    vector<bool> flag(A.size(), false);    int curMax = A[0];    for(int i = 0 ; i <  A.size(); ++ i){        if(A[i]>=curMax){            curMax = A[i];            flag[i] = true;        }    }    int curMin = A[A.size()-1];    for(int i = A.size()-1; i >=0; -- i ){        if(A[i] <= curMin){            curMin = A[i];            if(flag[i]) return i;        }    }    return -1;}